|
|
My program passes all tests created by me, so I don't know what could be the problem with it I tried test 1 given in task on my computer and got the same answer. But i get WA #1 wwhen submit * Clarification in problem statements: For any pair of crossroads no two segments of the same category connect these crossroads. * Tests not satisfing this condition are corrected. * The first test is changed to the sample from the problem statements. * New time limit is 2.5 seconds (old time limit was 3 seconds). * New memory limit is 64 MB (old memory limit was 16 MB). * New tests are added All solutions are rejudged. More than 100 authors lost AC during this rejudge. * Clarification in problem statements: For any pair of crossroads no two segments of the same category connect these crossroads. Sample test 0 2 0 0 2 1 is this true? * Clarification in problem statements: For any pair of crossroads no two segments of the same category connect these crossroads. Sample test 0 2 0 0 2 1 is this true? Yes, of course! If you got TLE, try change adjacency matrix to edge list. Bitset<30> operation "|" helps to avoid inner N-loop = 、= Using edge list, got TLE. I got AC changed edge list to adjacency matrix. Of course, with a little optimizations :) But not (2 ^ k) * (n ^ 2) * K : )) I sort the the 2^k states by the bits it contains, then check the states in order, and always TLE #22 Then, I choose a state randomly in the 2^k states and check if it's legal, and get accepted…… part of my code: 63 int ans = (1 << k) - 1; 64 int tot = 1 << k; 65 int times = 0; 66 while (tot > 0 && (times * realm < (500000000))) { 67 int now = rand() % tot; 68 if (countBit(arr[now]) < countBit(ans)){ 69 memset(visit,0,sizeof(visit)); 70 times++; 71 if (dfs(0,arr[now])) { 72 ans = arr[now]; 73 } 74 } 75 arr[now] = arr[--tot]; 76 } If you use G++, it's better to use standart function (__builtin_popcount(n)) instead of countBit(n) need some test plz. no idea whats wrong. thanks. As far as I know, 14 requires the maximum of 20 licenses - which may or may not be an issue for you. It was why I got WA 14. thank you. It is indeed the issue i have. I have AC with time 0.953sec, but my solution runs >2sec on a test generated by the following program: #include <cstdio> int main(){ int k = 20; int n = 30; int m = k+k*(((n-k)*(n-k-1))/2); printf("%d %d %d\n",k,n,m); for (int i = 1; i <= k; i++){ printf("%d %d %d\n",i,i+1,i-1); } for (int i = k+1; i < n; i++){ for (int j = i+1; j < n; j++){ for (int l = 0; l < k; l++){ printf("%d %d %d\n",i,j,l); } } for (int l = 0; l < k; l++){ printf("%d %d %d\n",i,0,l); } } return 0; } Admins, please respond. Was the test added? Admins! Please respond! :) Edited by author 08.12.2010 18:16 Thank you for test. It was added and the problem was rejudged. 69 authors lost AC. Great, thanks, I also lost AC :) N*(N+1)/2 It is not actual. Possibly K*N*(N+1)/2. It's also not actual. It seems to me test#20 has multiedges. In that case M is not limited at all )))) Give me some tests or write if there are some sly tests. I solve this problem by 2^K*N*N. I have the same problem. Where is bag? Edited by author 09.07.2008 23:49 Also WA8. Give some tests WA8. Small Code, but can not find any bug/ [code cut] Edited by moderator 18.04.2013 21:14 My solution is O(2^k). I think, that main problem's are - how reduce amount of DFS (check the route existence's with current set of licenses) and reduce brute-force to find all possible combinations of licenses. Binary search for number of licenses helped me to avoid TLE. Edited by author 08.01.2010 01:39 I am trying to take all possible combinations of k and run union-find to check if 0-1 are connected in that combinations. complexity is O(M(2^K)). is there a faster approach? Edited by author 16.08.2008 01:01 K==20 at test #1 And the answer for this test is "2\n0 2", as in the sample Is this test correct? Edited by author 15.02.2007 00:05 You are right. If K would be 20 for the sample test, then the answer will remain the same. I keep receiving WA1 here. Is the 1 test like the sample (except for the K = 20) ? On my machine I'm getting answer as the sample's one Problem statement was updated: • "N >= 2" instead of "N >= 1" • "Crossroads are numbered from 0 to N – 1, categories are numbered from 0 to K – 1" New tests have been added. Timelimit was decreased to 3 seconds. Submissions made after contest have been rejudged. |
|
|