Show all threads Hide all threads Show all messages Hide all messages |
Problem | jackkiu158 | 1045. Funny Game | 1 Nov 2017 13:23 | 1 |
Problem jackkiu158 1 Nov 2017 13:23 If start from all the leaf airport that from one airport could win, start from this airport suerly will lose. Otherwise,he could win. |
The test #10 | liudy | 1045. Funny Game | 4 Aug 2016 08:44 | 1 |
May be test 10 is something like 3 2 1 2 2 3 First player loses The start airport just has one airport connected. |
WA#8 | Juan Pablo | 1045. Funny Game | 6 May 2016 21:27 | 1 |
WA#8 Juan Pablo 6 May 2016 21:27 my code is wrong in the test 8 but i dont know the test, can you help me? |
HELP! I got WA10 | Felix_Mate | 1045. Funny Game | 9 Sep 2015 09:55 | 2 |
Edited by author 11.07.2015 20:44 I got run time error at #10 -_- |
WA #15 | Xysia | 1045. Funny Game | 29 Jan 2015 13:46 | 3 |
WA #15 Xysia 28 Jun 2009 00:06 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 |
Some hint about this problem. | Y.Y.M. | 1045. Funny Game | 11 Jan 2015 11:03 | 2 |
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 |
Is test #8 form the problem 1045 a special one? | Bogdan A. Stoica [fireatmyself] | 1045. Funny Game | 20 Sep 2012 14:29 | 4 |
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 |
Does any body know test #3? | Sid | 1045. Funny Game | 17 Jan 2012 16:58 | 7 |
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 |
No subject | Irina | 1045. Funny Game | 15 Jan 2012 02:57 | 1 |
Edited by author 08.04.2012 20:51 |
Accepted code. | Jumbo | 1045. Funny Game | 31 Dec 2011 01:36 | 1 |
#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; } |
WA#7 | Vilius Pranckaitis | 1045. Funny Game | 19 Sep 2011 16:32 | 1 |
WA#7 Vilius Pranckaitis 19 Sep 2011 16:32 Could anybody give me the input data? I have no idea what's wrong with my program. |
Does any body know test #12? | 504796440 | 1045. Funny Game | 13 Jul 2011 13:07 | 2 |
The starting node may have no neighbour. |
Can every one tell me why the simple output is that??? | 黄源河 | 1045. Funny Game | 3 Jun 2009 11:27 | 7 |
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! |
Please add these tests | LSBG | 1045. Funny Game | 13 May 2009 14:17 | 6 |
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 |
No subject | Xysia | 1045. Funny Game | 5 Feb 2009 16:42 | 1 |
Edited by author 23.02.2009 21:22 |
O,I need help,can you tell me why this wrong,thank you | sherry | 1045. Funny Game | 31 Jul 2008 14:05 | 2 |
#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... |
Who can tell me what does WA#2 means? | BurningARTs | 1045. Funny Game | 10 Jul 2008 05:19 | 2 |
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 |
Could someone tell me what case #10 is | ZhangTa | 1045. Funny Game | 27 Dec 2006 20:07 | 1 |
I don't know why I got WA Edited by author 27.12.2006 20:22 |
There may be something wrong in the test #6, plz check it, admin. | RoBa | 1045. Funny Game | 17 Aug 2006 15:01 | 2 |
I suspect there is something redundance after this test case, i.e, there is more than N-1 lines after the first line. Fixed (-) Vladimir Yakovlev (USU) 17 Aug 2006 15:01 |
std::vector<bool> crashes at 6th test! | Practician | 1045. Funny Game | 28 Jan 2006 16:30 | 5 |
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. |