# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
155452 | 2019-09-28T11:32:56 Z | Lawliet | Ball Machine (BOI13_ballmachine) | C++14 | 1000 ms | 25208 KB |
#include <bits/stdc++.h> #define LOG 20 #define MAX 100010 using namespace std; int n, q; int root; int n1, n2; int curTime; int ord[MAX]; int mnSub[MAX]; int dp[LOG][MAX]; bool hasBall[MAX]; vector<int> grafo[MAX]; set<int> s; struct cmp { bool operator () (int a, int b) { return ord[a] < ord[b]; } }; set<int , cmp> nextNode; void DFSInit(int cur) { mnSub[ cur ] = cur; for(int i = 0 ; i < grafo[ cur ].size() ; i++) DFSInit( grafo[ cur ][ i ] ); sort( grafo[ cur ].begin() , grafo[ cur ].end() , [&] (int a, int b) { return mnSub[ a ] < mnSub[ b ]; }); if( !grafo[cur].empty() ) mnSub[ cur ] = min(cur , mnSub[ grafo[cur][0] ]); } void DFSTour(int cur) { for(int i = 0 ; i < grafo[ cur ].size() ; i++) DFSTour( grafo[cur][i] ); ord[ cur ] = ++curTime; } int add(int k) { int last; while(k-- > 0) { last = *nextNode.begin(); nextNode.erase( nextNode.begin() ); hasBall[ last ] = true; } return last; } int pop(int i) { int d = 0; for(int k = LOG - 1 ; k >= 0 ; k--) { int jump = dp[ k ][ i ]; if(hasBall[ jump ]) { i = jump; d += (1 << k); } } nextNode.insert( i ); hasBall[ i ] = false; return d; } int main() { scanf("%d %d",&n,&q); for(int i = 1 ; i <= n ; i++) { scanf("%d",&dp[0][i]); if(dp[0][i] == 0) root = i; grafo[ dp[0][i] ].push_back( i ); } for(int k = 1 ; k < LOG ; k++) { for(int i = 1 ; i <= n ; i++) { int jump = dp[k - 1][ i ]; dp[k][ i ] = dp[k - 1][ jump ]; } } DFSInit( 1 ); DFSTour( 1 ); for(int i = 1 ; i <= n ; i++) nextNode.insert( i ); for(int i = 1 ; i <= q ; i++) { scanf("%d %d",&n1,&n2); if(n1 == 1) printf("%d\n",add( n2 )); if(n1 == 2) printf("%d\n",pop( n2 )); } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1046 ms | 2808 KB | Time limit exceeded |
2 | Execution timed out | 1094 ms | 9712 KB | Time limit exceeded |
3 | Incorrect | 65 ms | 10360 KB | Output isn't correct |
4 | Execution timed out | 1070 ms | 2808 KB | Time limit exceeded |
5 | Execution timed out | 1094 ms | 2808 KB | Time limit exceeded |
6 | Execution timed out | 1051 ms | 2936 KB | Time limit exceeded |
7 | Execution timed out | 1054 ms | 2936 KB | Time limit exceeded |
8 | Execution timed out | 1038 ms | 2808 KB | Time limit exceeded |
9 | Execution timed out | 1058 ms | 3192 KB | Time limit exceeded |
10 | Execution timed out | 1055 ms | 4600 KB | Time limit exceeded |
11 | Execution timed out | 1084 ms | 9720 KB | Time limit exceeded |
12 | Incorrect | 62 ms | 10360 KB | Output isn't correct |
13 | Execution timed out | 1074 ms | 9468 KB | Time limit exceeded |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 53 ms | 7820 KB | Output isn't correct |
2 | Execution timed out | 1065 ms | 17400 KB | Time limit exceeded |
3 | Incorrect | 75 ms | 13044 KB | Output isn't correct |
4 | Execution timed out | 1024 ms | 6264 KB | Time limit exceeded |
5 | Execution timed out | 1016 ms | 6008 KB | Time limit exceeded |
6 | Execution timed out | 1014 ms | 6008 KB | Time limit exceeded |
7 | Execution timed out | 1053 ms | 5880 KB | Time limit exceeded |
8 | Incorrect | 53 ms | 7804 KB | Output isn't correct |
9 | Execution timed out | 1028 ms | 21196 KB | Time limit exceeded |
10 | Execution timed out | 1062 ms | 17400 KB | Time limit exceeded |
11 | Execution timed out | 1061 ms | 13176 KB | Time limit exceeded |
12 | Execution timed out | 1044 ms | 13032 KB | Time limit exceeded |
13 | Incorrect | 104 ms | 17580 KB | Output isn't correct |
14 | Incorrect | 65 ms | 13168 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1020 ms | 11128 KB | Time limit exceeded |
2 | Execution timed out | 1057 ms | 16968 KB | Time limit exceeded |
3 | Execution timed out | 1068 ms | 15480 KB | Time limit exceeded |
4 | Execution timed out | 1065 ms | 11512 KB | Time limit exceeded |
5 | Execution timed out | 1058 ms | 11212 KB | Time limit exceeded |
6 | Execution timed out | 1083 ms | 11208 KB | Time limit exceeded |
7 | Execution timed out | 1078 ms | 14584 KB | Time limit exceeded |
8 | Execution timed out | 1069 ms | 15480 KB | Time limit exceeded |
9 | Execution timed out | 1066 ms | 13560 KB | Time limit exceeded |
10 | Execution timed out | 1044 ms | 13160 KB | Time limit exceeded |
11 | Execution timed out | 1034 ms | 15480 KB | Time limit exceeded |
12 | Execution timed out | 1048 ms | 17016 KB | Time limit exceeded |
13 | Execution timed out | 1043 ms | 17400 KB | Time limit exceeded |
14 | Execution timed out | 1046 ms | 12792 KB | Time limit exceeded |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1079 ms | 13688 KB | Time limit exceeded |
2 | Execution timed out | 1075 ms | 18040 KB | Time limit exceeded |
3 | Incorrect | 170 ms | 25208 KB | Output isn't correct |
4 | Execution timed out | 1071 ms | 13660 KB | Time limit exceeded |
5 | Execution timed out | 1074 ms | 13176 KB | Time limit exceeded |
6 | Incorrect | 191 ms | 21692 KB | Output isn't correct |
7 | Execution timed out | 1061 ms | 18168 KB | Time limit exceeded |
8 | Incorrect | 179 ms | 25020 KB | Output isn't correct |
9 | Incorrect | 74 ms | 13044 KB | Output isn't correct |