# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
346731 | 2021-01-10T20:28:22 Z | CaroLinda | Bitaro’s Party (JOI18_bitaro) | C++14 | 1816 ms | 425488 KB |
#include <bits/stdc++.h> #define ll long long #define sz(x) x.size() #define all(x) x.begin(),x.end() const int MAXN = 1e5+10 ; const int MAGIC = 317 ; using namespace std ; int N , M , Q ; int T[MAXN] ; vector<int> adj[MAXN] ; vector<int> occupied[MAXN] ; int ansQuery[MAXN] ; vector< pair<int,int> > farFromMe[MAXN] ; bool freq[MAXN] ; vector<int> lightQueries[MAXN] , heavyQueries[MAXN] ; int dp[MAXN] ; int main() { scanf("%d %d %d", &N, &M, &Q ) ; for(int i = 1 , u ,v ; i <= M ; i++ ) { scanf("%d %d", &u, &v ) ; if( u < v ) swap(u,v) ; adj[u].push_back(v) ; } for(int i = 1 ,t , y, x ; i <= Q ; i++ ) { scanf("%d %d", &t , &y ) ; for(int j = 0 ; j < y ; j++ ) { scanf("%d", &x ) ; occupied[i].push_back(x) ; } if( y < MAGIC ) lightQueries[ t ].push_back(i) ; else heavyQueries[t].push_back(i) ; ansQuery[i] = -1 ; } for(int i = 1 ; i <= N ; i++ ) { for(auto e : adj[i] ) { int idxMe = 0 , idxThem = 0 ; vector<pair<int,int> > aux ; while( (idxMe < sz(farFromMe[i]) || idxThem < sz(farFromMe[e] ) ) && sz(aux) < MAGIC ) { if( idxThem < sz(farFromMe[e] ) && freq[ farFromMe[e][idxThem].second ] ) { idxThem++ ; continue ; } if( idxMe < sz(farFromMe[i] ) && freq[ farFromMe[i][idxMe].second ] ) { idxMe++ ; continue ; } if( idxMe == sz(farFromMe[i] ) || (idxThem < sz(farFromMe[e] ) && farFromMe[e][idxThem].first+1 >= farFromMe[i][idxMe].first ) ) { aux.push_back( make_pair(farFromMe[e][idxThem].first+1, farFromMe[e][idxThem].second ) ) ; idxThem++ ; } else { aux.push_back( farFromMe[i][idxMe] ) ; idxMe++ ; } freq[ aux.back().second ] = true ; } for(auto e : aux ) freq[e.second ] = false ; swap(farFromMe[i], aux) ; } if( sz(farFromMe[i] ) < MAGIC ) farFromMe[i].push_back( make_pair(0, i) ) ; for(auto party : lightQueries[i] ) { for(auto e : occupied[party] ) freq[e] = true ; for(int j = 0 ; j < sz(farFromMe[i] ) ; j++ ) { if( freq[ farFromMe[i][j].second ] ) continue ; ansQuery[ party ] = farFromMe[i][j].first ; break ; } for(auto e : occupied[ party ] ) freq[e] = false ; } } /* for(int i= 1 ; i <= N ; i++ ) { cout << i << endl ; for(auto e : farFromMe[i] ) cout << e.first << " " << e.second << endl ; cout << endl ; } */ for(int i = 1 ; i <= N ; i++ ) for(auto party : heavyQueries[i] ) { for(auto e : occupied[party] ) freq[e] = true ; for(int j = 1 ; j <= i ; j++ ) { dp[j] = freq[j] ? -1 : 0 ; for(auto e : adj[j] ) if( dp[e] != -1 ) dp[j] = max(dp[j], dp[e]+1 ) ; } for(auto e : occupied[party] ) freq[e] = false ; ansQuery[party] = dp[i] ; } for(int i = 1 ; i <= Q ; i++ ) printf("%d\n", ansQuery[i] ) ; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 12268 KB | Output is correct |
2 | Correct | 8 ms | 12140 KB | Output is correct |
3 | Correct | 8 ms | 12140 KB | Output is correct |
4 | Correct | 9 ms | 12140 KB | Output is correct |
5 | Correct | 11 ms | 12524 KB | Output is correct |
6 | Correct | 11 ms | 12524 KB | Output is correct |
7 | Correct | 11 ms | 12524 KB | Output is correct |
8 | Correct | 23 ms | 15468 KB | Output is correct |
9 | Correct | 22 ms | 15468 KB | Output is correct |
10 | Correct | 22 ms | 15468 KB | Output is correct |
11 | Correct | 20 ms | 15084 KB | Output is correct |
12 | Correct | 15 ms | 13420 KB | Output is correct |
13 | Correct | 20 ms | 14828 KB | Output is correct |
14 | Correct | 20 ms | 14060 KB | Output is correct |
15 | Correct | 15 ms | 13036 KB | Output is correct |
16 | Correct | 19 ms | 14060 KB | Output is correct |
17 | Correct | 19 ms | 14336 KB | Output is correct |
18 | Correct | 16 ms | 13548 KB | Output is correct |
19 | Correct | 19 ms | 14316 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 12268 KB | Output is correct |
2 | Correct | 8 ms | 12140 KB | Output is correct |
3 | Correct | 8 ms | 12140 KB | Output is correct |
4 | Correct | 9 ms | 12140 KB | Output is correct |
5 | Correct | 11 ms | 12524 KB | Output is correct |
6 | Correct | 11 ms | 12524 KB | Output is correct |
7 | Correct | 11 ms | 12524 KB | Output is correct |
8 | Correct | 23 ms | 15468 KB | Output is correct |
9 | Correct | 22 ms | 15468 KB | Output is correct |
10 | Correct | 22 ms | 15468 KB | Output is correct |
11 | Correct | 20 ms | 15084 KB | Output is correct |
12 | Correct | 15 ms | 13420 KB | Output is correct |
13 | Correct | 20 ms | 14828 KB | Output is correct |
14 | Correct | 20 ms | 14060 KB | Output is correct |
15 | Correct | 15 ms | 13036 KB | Output is correct |
16 | Correct | 19 ms | 14060 KB | Output is correct |
17 | Correct | 19 ms | 14336 KB | Output is correct |
18 | Correct | 16 ms | 13548 KB | Output is correct |
19 | Correct | 19 ms | 14316 KB | Output is correct |
20 | Correct | 886 ms | 18248 KB | Output is correct |
21 | Correct | 861 ms | 18156 KB | Output is correct |
22 | Correct | 863 ms | 18260 KB | Output is correct |
23 | Correct | 944 ms | 18400 KB | Output is correct |
24 | Correct | 1294 ms | 261864 KB | Output is correct |
25 | Correct | 1370 ms | 273512 KB | Output is correct |
26 | Correct | 1367 ms | 272476 KB | Output is correct |
27 | Correct | 1643 ms | 420172 KB | Output is correct |
28 | Correct | 1662 ms | 420324 KB | Output is correct |
29 | Correct | 1645 ms | 420328 KB | Output is correct |
30 | Correct | 1630 ms | 419480 KB | Output is correct |
31 | Correct | 1641 ms | 405404 KB | Output is correct |
32 | Correct | 1646 ms | 419688 KB | Output is correct |
33 | Correct | 1274 ms | 261868 KB | Output is correct |
34 | Correct | 1118 ms | 216096 KB | Output is correct |
35 | Correct | 1269 ms | 260320 KB | Output is correct |
36 | Correct | 1553 ms | 341004 KB | Output is correct |
37 | Correct | 1470 ms | 309020 KB | Output is correct |
38 | Correct | 1560 ms | 341980 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 12268 KB | Output is correct |
2 | Correct | 8 ms | 12140 KB | Output is correct |
3 | Correct | 8 ms | 12140 KB | Output is correct |
4 | Correct | 9 ms | 12140 KB | Output is correct |
5 | Correct | 11 ms | 12524 KB | Output is correct |
6 | Correct | 11 ms | 12524 KB | Output is correct |
7 | Correct | 11 ms | 12524 KB | Output is correct |
8 | Correct | 23 ms | 15468 KB | Output is correct |
9 | Correct | 22 ms | 15468 KB | Output is correct |
10 | Correct | 22 ms | 15468 KB | Output is correct |
11 | Correct | 20 ms | 15084 KB | Output is correct |
12 | Correct | 15 ms | 13420 KB | Output is correct |
13 | Correct | 20 ms | 14828 KB | Output is correct |
14 | Correct | 20 ms | 14060 KB | Output is correct |
15 | Correct | 15 ms | 13036 KB | Output is correct |
16 | Correct | 19 ms | 14060 KB | Output is correct |
17 | Correct | 19 ms | 14336 KB | Output is correct |
18 | Correct | 16 ms | 13548 KB | Output is correct |
19 | Correct | 19 ms | 14316 KB | Output is correct |
20 | Correct | 886 ms | 18248 KB | Output is correct |
21 | Correct | 861 ms | 18156 KB | Output is correct |
22 | Correct | 863 ms | 18260 KB | Output is correct |
23 | Correct | 944 ms | 18400 KB | Output is correct |
24 | Correct | 1294 ms | 261864 KB | Output is correct |
25 | Correct | 1370 ms | 273512 KB | Output is correct |
26 | Correct | 1367 ms | 272476 KB | Output is correct |
27 | Correct | 1643 ms | 420172 KB | Output is correct |
28 | Correct | 1662 ms | 420324 KB | Output is correct |
29 | Correct | 1645 ms | 420328 KB | Output is correct |
30 | Correct | 1630 ms | 419480 KB | Output is correct |
31 | Correct | 1641 ms | 405404 KB | Output is correct |
32 | Correct | 1646 ms | 419688 KB | Output is correct |
33 | Correct | 1274 ms | 261868 KB | Output is correct |
34 | Correct | 1118 ms | 216096 KB | Output is correct |
35 | Correct | 1269 ms | 260320 KB | Output is correct |
36 | Correct | 1553 ms | 341004 KB | Output is correct |
37 | Correct | 1470 ms | 309020 KB | Output is correct |
38 | Correct | 1560 ms | 341980 KB | Output is correct |
39 | Correct | 1422 ms | 270316 KB | Output is correct |
40 | Correct | 1353 ms | 269036 KB | Output is correct |
41 | Correct | 1355 ms | 271212 KB | Output is correct |
42 | Correct | 1416 ms | 268908 KB | Output is correct |
43 | Correct | 1353 ms | 268532 KB | Output is correct |
44 | Correct | 932 ms | 22380 KB | Output is correct |
45 | Correct | 889 ms | 19420 KB | Output is correct |
46 | Correct | 878 ms | 19052 KB | Output is correct |
47 | Correct | 893 ms | 18540 KB | Output is correct |
48 | Correct | 871 ms | 18156 KB | Output is correct |
49 | Correct | 1737 ms | 425452 KB | Output is correct |
50 | Correct | 1651 ms | 420204 KB | Output is correct |
51 | Correct | 909 ms | 22252 KB | Output is correct |
52 | Correct | 872 ms | 19180 KB | Output is correct |
53 | Correct | 1642 ms | 344484 KB | Output is correct |
54 | Correct | 1566 ms | 314548 KB | Output is correct |
55 | Correct | 1562 ms | 340412 KB | Output is correct |
56 | Correct | 1480 ms | 310776 KB | Output is correct |
57 | Correct | 924 ms | 22380 KB | Output is correct |
58 | Correct | 928 ms | 22252 KB | Output is correct |
59 | Correct | 865 ms | 19052 KB | Output is correct |
60 | Correct | 874 ms | 18924 KB | Output is correct |
61 | Correct | 1720 ms | 420716 KB | Output is correct |
62 | Correct | 1625 ms | 341868 KB | Output is correct |
63 | Correct | 1564 ms | 309452 KB | Output is correct |
64 | Correct | 1816 ms | 420844 KB | Output is correct |
65 | Correct | 1719 ms | 340844 KB | Output is correct |
66 | Correct | 1650 ms | 311532 KB | Output is correct |
67 | Correct | 1651 ms | 420332 KB | Output is correct |
68 | Correct | 1567 ms | 341484 KB | Output is correct |
69 | Correct | 1473 ms | 306796 KB | Output is correct |
70 | Correct | 1659 ms | 420648 KB | Output is correct |
71 | Correct | 1578 ms | 341908 KB | Output is correct |
72 | Correct | 1498 ms | 310636 KB | Output is correct |
73 | Correct | 1666 ms | 420844 KB | Output is correct |
74 | Correct | 1604 ms | 342136 KB | Output is correct |
75 | Correct | 1502 ms | 310764 KB | Output is correct |
76 | Correct | 1734 ms | 425488 KB | Output is correct |
77 | Correct | 1642 ms | 420716 KB | Output is correct |
78 | Correct | 1647 ms | 420972 KB | Output is correct |
79 | Correct | 907 ms | 22252 KB | Output is correct |
80 | Correct | 861 ms | 19052 KB | Output is correct |
81 | Correct | 848 ms | 18316 KB | Output is correct |
82 | Correct | 1739 ms | 425160 KB | Output is correct |
83 | Correct | 1766 ms | 410860 KB | Output is correct |
84 | Correct | 1659 ms | 420204 KB | Output is correct |
85 | Correct | 1660 ms | 405460 KB | Output is correct |
86 | Correct | 1652 ms | 420204 KB | Output is correct |
87 | Correct | 1677 ms | 406484 KB | Output is correct |
88 | Correct | 917 ms | 22124 KB | Output is correct |
89 | Correct | 925 ms | 22144 KB | Output is correct |
90 | Correct | 860 ms | 19052 KB | Output is correct |
91 | Correct | 869 ms | 19052 KB | Output is correct |
92 | Correct | 875 ms | 18156 KB | Output is correct |
93 | Correct | 883 ms | 18304 KB | Output is correct |
94 | Correct | 1358 ms | 267500 KB | Output is correct |
95 | Correct | 1206 ms | 219884 KB | Output is correct |
96 | Correct | 1290 ms | 261356 KB | Output is correct |
97 | Correct | 1131 ms | 219416 KB | Output is correct |
98 | Correct | 1290 ms | 262380 KB | Output is correct |
99 | Correct | 1132 ms | 218732 KB | Output is correct |
100 | Correct | 981 ms | 22276 KB | Output is correct |
101 | Correct | 988 ms | 22252 KB | Output is correct |
102 | Correct | 923 ms | 19052 KB | Output is correct |
103 | Correct | 936 ms | 19180 KB | Output is correct |
104 | Correct | 910 ms | 18284 KB | Output is correct |
105 | Correct | 921 ms | 18412 KB | Output is correct |
106 | Correct | 1657 ms | 345196 KB | Output is correct |
107 | Correct | 1562 ms | 315116 KB | Output is correct |
108 | Correct | 1554 ms | 342636 KB | Output is correct |
109 | Correct | 1466 ms | 310020 KB | Output is correct |
110 | Correct | 1576 ms | 342776 KB | Output is correct |
111 | Correct | 1485 ms | 311148 KB | Output is correct |
112 | Correct | 919 ms | 22380 KB | Output is correct |
113 | Correct | 929 ms | 22252 KB | Output is correct |
114 | Correct | 858 ms | 19052 KB | Output is correct |
115 | Correct | 876 ms | 19432 KB | Output is correct |
116 | Correct | 881 ms | 18136 KB | Output is correct |
117 | Correct | 867 ms | 18156 KB | Output is correct |
118 | Correct | 1639 ms | 420392 KB | Output is correct |
119 | Correct | 1575 ms | 342380 KB | Output is correct |
120 | Correct | 1494 ms | 309700 KB | Output is correct |
121 | Correct | 1660 ms | 420588 KB | Output is correct |
122 | Correct | 1585 ms | 341160 KB | Output is correct |
123 | Correct | 1476 ms | 310124 KB | Output is correct |
124 | Correct | 1640 ms | 420204 KB | Output is correct |
125 | Correct | 1577 ms | 342380 KB | Output is correct |
126 | Correct | 1476 ms | 308836 KB | Output is correct |