제출 #1020141

#제출 시각아이디문제언어결과실행 시간메모리
1020141dostsBitaro’s Party (JOI18_bitaro)C++17
7 / 100
1408 ms524288 KiB
//Dost SEFEROĞLU #include <bits/stdc++.h> using namespace std; #define int long long #define pii pair<int,int> #define ff first #define ss second #define sp << " " << #define vi vector<int> #define all(xx) xx.begin(),xx.end() #define ps(xxx) cout << (xxx) << endl; const int N = 1e5+1,inf = 1e18,MOD = 998244353,B = 350; vi edges[N],egdes[N]; vector<pii> mfs[N]; vi vis(N,0); vi best(N); vi order; void topo(int node) { if (vis[node]) return; vis[node] = 1; for (auto it : egdes[node]) topo(it); order.push_back(node); } void calc() { for (int i=0;i<order.size();i++) { int node = order[i]; vector<pii> ps; vi allnbs; for (auto it : egdes[node]) { for (auto itt : mfs[it]) { if (!best[itt.ss]) allnbs.push_back(itt.ss); best[itt.ss] = max(best[itt.ss],itt.ff+1); } } for (auto it : allnbs) ps.push_back({best[it],it}); if (!ps.empty()) sort(all(ps),greater<pii>()); if (ps.size() > B+5) ps.resize(B+5); swap(mfs[node],ps); mfs[node].push_back({0,node}); for (auto it : egdes[node]) for (auto itt : mfs[it]) best[itt.ss] = 0; } } vi mxdist(N); void bfs2(int root) { mxdist[root] = 0; for (int i=order.size()-1;i>=0;i--) { int f = order[i]; if (f != root) mxdist[f] = -1; for (auto it : edges[f]) if(mxdist[it]!=-1) mxdist[f] = max(mxdist[f],mxdist[it]+1); } } void solve() { int n,m,q; cin >> n >> m >> q; for (int i=1;i<=m;i++) { int a,b; cin >> a >> b; edges[a].push_back(b); egdes[b].push_back(a); } for (int i=1;i<=n;i++) topo(i); calc(); vi banned(n+1,0); while (q--) { int node,k; cin >> node >> k; vi c(k+1); for (int i=1;i<=k;i++) cin >> c[i]; for (int i=1;i<=k;i++) banned[c[i]] = 1; if (k <= B) { bool fl = 0; for (auto it : mfs[node]) { if (!banned[it.ss]) { fl = 1; cout << it.ff << endl; break; } } if (!fl) cout << -1 << endl; } else { mxdist.assign(n+1,-1); bfs2(node); int ans = -1; for (int i=1;i<=n;i++) if (!banned[i]) ans = max(ans,mxdist[i]); cout << ans << '\n'; } for (int i=1;i<=k;i++) banned[c[i]] = 0; } } signed main() { ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); #ifdef Dodi freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); #endif int t = 1; //cin >> t; while (t --> 0) solve(); }

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

bitaro.cpp: In function 'void calc()':
bitaro.cpp:29:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for (int i=0;i<order.size();i++) {
      |                  ~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...