제출 #160418

#제출 시각아이디문제언어결과실행 시간메모리
160418combi1k1Bitaro’s Party (JOI18_bitaro)C++14
7 / 100
1558 ms524292 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 = 317; vector<int> g[N]; vector<ii> opt[N]; void pus(int u,int v) { int a = 0; int b = 0; for(ii &e : opt[v]) e.X++; vector<ii> clone; while (a < opt[u].size() && b < opt[v].size()) { if (opt[u][a] < opt[v][b]) clone.pb(opt[v][b++]); else clone.pb(opt[u][a++]); } while (a < opt[u].size()) clone.pb(opt[u][a++]); while (b < opt[v].size()) clone.pb(opt[v][b++]); clone.resize(unique(clone.begin(),clone.end()) - clone.begin()); while (clone.size() > B) clone.pop_back(); for(ii &e : opt[v]) e.X--; opt[u].swap(clone); } int vis[N]; int ban[N]; int len[N]; 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); pus(u,v); } } int cal(int u) { if (vis[u]) return len[u]; len[u] = (ban[u] ? -N : 0); vis[u] = 1; 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; if (k < B) { for(ii e : opt[u]) if(!ban[e.Y]) ans = max(ans,e.X); } else { fill(vis + 1,vis + 1 + n,0); 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 */

컴파일 시 표준 에러 (stderr) 메시지

bitaro.cpp: In function 'void pus(int, int)':
bitaro.cpp:26:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (a < opt[u].size() && b < opt[v].size())  {
            ~~^~~~~~~~~~~~~~~
bitaro.cpp:26:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (a < opt[u].size() && b < opt[v].size())  {
                                 ~~^~~~~~~~~~~~~~~
bitaro.cpp:32:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (a < opt[u].size())   clone.pb(opt[u][a++]);
            ~~^~~~~~~~~~~~~~~
bitaro.cpp:33:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (b < opt[v].size())   clone.pb(opt[v][b++]);
            ~~^~~~~~~~~~~~~~~
bitaro.cpp: In function 'int dfs(int)':
bitaro.cpp:58: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...