If start from all the leaf airport that from one airport could win, start from this airport suerly will lose. Otherwise,he could win. May be test 10 is something like 3 2 1 2 2 3 First player loses The start airport just has one airport connected. my code is wrong in the test 8 but i dont know the test, can you help me? Edited by author 11.07.2015 20:44 I got run time error at #10 -_- ok, now I have AC :) Edited by author 29.06.2009 17:03 If you have WA15, try this test: 5 1 1 3 1 2 1 4 1 1 My AC program outputs: First player wins flying to airport 2 Read carefully: "...If there are several such airports, the program should find one of them that has the minimal number..." Tnx :) it helped! but your test data shoud be: 5 1 1 3 1 2 1 4 1 5 :D 1. If we regard the start airport as the root,it is clear that the graph is a tree. 2. If start from all the leaf airport that from one airport could win, start from this airport suerly will lose. Otherwise,he could win. 3. We use a flag to record start from one airport will win or not.Just DFS to obtain all flag. In this way,you could get AC in O(e). Is there any better way to solve this problem? I think the answer is yes. So,could you write down your thought? I didn't want to create new thread, so I will just revive this thread. My idead was to use simple minimax algorithm: boolean firstWins(node v) for every neighbour u of node v check secondWins(u) return true if for some u second loses return false boolean secondWins(node v) for every neighbour u of node v check firstWins(u) return true if for some u first loses return false Hope it will be helpful to someone. Edited by author 11.01.2015 11:04 I submited several times and i got WA at test #8. I really appreciate if you would be so kind by giving me test #8. Thank you. Edited by author 30.09.2005 16:11 Edited by author 30.09.2005 16:11 it help you 5 1 1 2 2 3 2 4 4 5 Good luck P.S. I think you program Wrong. Guy who create test 99% very funny. The answer is "First player loses". That's why each terrorist chooses the best move. It's tricky TestCase. Thankx, it help you 5 1 1 2 2 3 2 4 4 5 Good luck P.S. I think you program Wrong. Guy who create test 99% very funny. I have changed my code several times...This one is always wrong. One time it's correct , but other testcases are all wrong. Finally after I add more 30 lines, I got AC . My code is very ugly I got WA#3 and can't anderstand why... Edited by author 08.04.2005 22:01 Here it is: 11 8 1 3 1 2 2 4 4 5 4 6 2 8 8 9 8 7 9 10 10 11 Thank you guys! In fackt I didn't anderstand task correctly... But now I got AC Edited by author 08.04.2005 22:02 11 8 1 3 1 2 2 4 4 5 4 6 2 8 8 9 8 7 9 10 10 11 ans: First player wins flying to airport 2 But I still can't understand why WA. Your answer is inccorect! answer mus be: First player wins flying to airport 3 "If there are several such airports, the program should find one of them that has the minimal number" But 2 is less than 3. So why not to fly to airport number 2? 2 is the correct answer my answer is 2 and my program is Accepted Edited by author 08.04.2012 20:51 #include <cstdio> #include <vector> #include <algorithm> using namespace std; vector < vector < int > > g; vector < bool > d; void dfs(int v, int p = -1) { if ((int)g[v].size()==1) d[v]=false; d[v] = false; for (int i = (int)g[v].size()-1; i >= 0; i--) { int to = g[v][i]; if (to == p) continue; dfs(to,v); if (!d[to]) d[v] = true; } } int main() { int n,root; scanf("%d%d",&n,&root); g.resize(n+1); d.resize(n+1); for (int i=1;i<=n-1;i++) { int u,v; scanf("%d%d",&u,&v); g[u].push_back(v); g[v].push_back(u); } for (int i=1;i<=n;i++) sort(g[i].begin(),g[i].end());
dfs(root); if (d[root]) { for (int i = 0; i<(int)g[root].size(); i++) if (!d[g[root][i]]) { printf("First player wins flying to airport %d",g[root][i]); return 0;} } puts("First player loses"); return 0; } Could anybody give me the input data? I have no idea what's wrong with my program. The starting node may have no neighbour. Sample Input 4 3 3 2 3 1 1 4 Sample Output First player wins flying to airport 2 When players flies to the airport 2 the second player will not can make his move, and so first player wins. If they will fly to the airport 1 then first player loses, thus answer is unambiguous. Oh! I can't understand the problem at that time. Now,I know,the terrorists are move together. Now,I know,the terrorists are move together. 'are move' should be 'are moving'. :) Now I know.Thank you very much. Who are you??? I think it's not polite to use other people's name! Hello! My solution got accepted, but now as I thought it through it is wrong. Here are some tests that will fail me: Test 1: 6 3 1 2 2 3 4 5 5 6 6 3 Answer: First player wins flying to airport 6 Test 2: 15 12 1 2 2 3 4 5 5 6 6 3 3 11 7 8 8 9 9 10 10 11 11 12 13 12 14 13 15 14 Answer: First player wins flying to airport 11 Edited by author 09.05.2009 13:47 New tests were added and the problem was rejudged. If you have more good tests send them to timus_support (at)acm.timus.ru did you add some new test? give please - i got WA i've passed these testss but wa#15 after rejudgement... *confused* What failed my solution was that it didn't find the airport with a minimal number (try this: 3 1 1 3 1 2 Answer: First player wins flying to airport 2 ), it's kind of strange that there weren't such tests before Edited by author 23.02.2009 21:22 #include<stdio.h> #include<stdlib.h> #define MAX 1002 int join[MAX][MAX],cont[MAX],used[MAX],win[MAX]; int np,mark,fri; int tree(int aa) { int i,j,k,mar=0,min1=MAX,min2=MAX; used[aa]=1; if(cont[aa]==1&&aa!=fri)//!!cout为1可为终点,亦可为起点~!! { win[aa]=aa; return 0; } for(i=1;i<=np;i++) { if(join[aa][i]&&!used[i]) {
k=tree(i); if(!k&&min1>win[i]) { mar=1; min1=win[i]; } if(k&&min2>win[i]) min2=win[i]; } } if(mar) { win[aa]=min1; return 1; } else { win[aa]=min2; return 0; } } int main() { int i,j,k,mar=0; scanf("%d%d",&np,&fri); for(i=1;i<np;i++) { scanf("%d%d",&j,&k); join[j][k]=1; join[k][j]=1; cont[j]++; cont[k]++; } k=tree(fri); if(k)printf("First player wins flying to airport %d\n",win[fri]); else printf("First player loses\n"); // system("pause"); return 0; } I find where I made the mistake, I just misunderstand the porblem... Thx in advance! first player loses <- answer. It means that you have problem with second variant. use this simple test(it helped me): 3 3 3 2 2 1 first player loses I don't know why I got WA Edited by author 27.12.2006 20:22 I suspect there is something redundance after this test case, i.e, there is more than N-1 lines after the first line. Due to memory requirements I used std::vector<bool> arrays for storing node edges, but it chashes! (function std::vector<bool>::operator[](int), to be exact) Does anybody knows why? P.S. If I use, f.e., std::bitset<> instead, I get strong AC. Therefore, timus's std::vector<bool> has error, hasnt it? I suppose you cool programer if you use STL... By the way,is STL supported by timus C++ compiler? Are you funny? It is just convenient to use it instead of doing some things yourself. IMHO, timus must support STL as it is the part of C++ and it does. |
|