Submission #160431

#TimeUsernameProblemLanguageResultExecution timeMemory
160431combi1k1Bitaro’s Party (JOI18_bitaro)C++14
0 / 100
9 ms5496 KiB
#include<bits/stdc++.h> using namespace std; #define X first #define Y second #define pb push_back #define ii pair<int,int> #define FOR(i,a,b) for(int i = a ; i < b ; ++i) const int N = 1e5 + 1; const int B = 300; vector<int> g[N]; vector<ii> opt[N]; int vis[N]; int ban[N]; int len[N]; int tot = 1; void pus(int u,int v) { for(ii &e : opt[v]) e.X++; vector<ii> clone; auto add = [&](ii e) { if (vis[e.Y] != tot) vis[e.Y] = tot, clone.pb(e); }; int a = 0; int b = 0; while (a < opt[u].size() && b < opt[v].size()) { if (opt[u][a] < opt[v][b]) { add(opt[v][b++]); continue; } if (opt[u][a] > opt[v][b]) { add(opt[u][a++]); continue; } clone.pb(opt[u][a]); a++; b++; } while (a < opt[u].size()) add(opt[u][a++]); while (b < opt[v].size()) add(opt[v][b++]); while (clone.size() > B) clone.pop_back(); for(ii &e : opt[v]) e.X--; opt[u].swap(clone); } int dfs(int u) { if (vis[u]) return 0; vis[u] = 1; opt[u].pb(ii(0,u)); for(int v : g[u]) { dfs(v); tot++; pus(u,v); } } int cal(int u) { if (vis[u] == tot) return len[u]; vis[u] = tot; len[u] = ban[u] ? -N : 0; for(int v : g[u]) len[u] = max(len[u],cal(v) + 1); return len[u]; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; int m; cin >> m; int q; cin >> q; FOR(i,0,m) { int x; cin >> x; int y; cin >> y; g[y].pb(x); } FOR(i,1,n + 1) if(!vis[i]) dfs(i); FOR(i,1,q + 1) { int u; cin >> u; int k; cin >> k; vector<int> vv; FOR(i,0,k) { int x; cin >> x; ban[x] = 1; vv.pb(x); } int ans = -1; tot++; if (k < B) for(ii e : opt[u]) if(!ban[e.Y]) ans = max(ans,e.X); else ans = max(ans,cal(u)); for(int x : vv) ban[x] = 0; cout << ans << "\n"; } } /* 5 6 3 1 2 2 4 3 4 1 3 3 5 4 5 4 1 1 5 2 2 3 2 3 1 4 5 */

Compilation message (stderr)

bitaro.cpp: In function 'void pus(int, int)':
bitaro.cpp:36:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (a < opt[u].size() && b < opt[v].size())  {
            ~~^~~~~~~~~~~~~~~
bitaro.cpp:36:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (a < opt[u].size() && b < opt[v].size())  {
                                 ~~^~~~~~~~~~~~~~~
bitaro.cpp:44:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (a < opt[u].size())   add(opt[u][a++]);
            ~~^~~~~~~~~~~~~~~
bitaro.cpp:45:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (b < opt[v].size())   add(opt[v][b++]);
            ~~^~~~~~~~~~~~~~~
bitaro.cpp: In function 'int main()':
bitaro.cpp:106:12: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
         if (k < B)
            ^
bitaro.cpp: In function 'int dfs(int)':
bitaro.cpp:64:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...