제출 #396463

#제출 시각아이디문제언어결과실행 시간메모리
396463pure_memBitaro’s Party (JOI18_bitaro)C++14
14 / 100
1298 ms428420 KiB
#include <bits/stdc++.h> #define X first #define Y second #define MP make_pair #define ll long long using namespace std; const int N = 4e5 + 1, BS = 330; const ll INF = 1e18; int n, m, q, dsu[N], used[N], cnt[N], dp[N]; vector< int > g[N]; vector< pair<int, int> > gg[N]; int ptr[N]; void prep(){ cin >> n >> m >> q; for(int i = 1, x, y;i <= m;i++){ cin >> x >> y; g[y].push_back(x); } for(int i = 1;i <= n;i++){ for(int from: g[i]) ptr[from] = 0; while(gg[i].size() <= BS + 1){ int mx = -1; pair<int, int> need = MP(0, 0); for(int from: g[i]){ if(ptr[from] < gg[from].size() && (mx == -1 || need.X < gg[from][ptr[from]].X)) need = gg[from][ptr[from]], mx = from; } need.X++; if(mx == -1) break; else gg[i].push_back(need), ptr[mx]++; } if(gg[i].size() <= BS + 1) gg[i].push_back(MP(0, i)); sort(gg[i].begin(), gg[i].end(), [](pair<int, int> x, pair<int, int> y){ return x > y; }); } } int main () { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); prep(); for(int pos, len, x, T = N + 1;q--;T++){ cin >> pos >> len; for(int j = 1;j <= len;j++){ cin >> x, used[x] = T; } if(len > 300){ for(int i = 1;i <= pos;i++){ dp[i] = 0, cnt[i] = 0; if(used[i] != T) cnt[i] = 1; for(int from: g[i]){ if(dp[from] + 1 > dp[i] && cnt[from]) dp[i] = dp[from] + 1, cnt[i] = cnt[from]; else if(dp[from] + 1 == dp[i] && cnt[from]) cnt[i]++; } } } else { dp[pos] = 0, cnt[pos] = 0; for(pair<int, int> tmp: gg[pos]){ if(used[tmp.Y] == T) continue; if(tmp.X > dp[pos]) dp[pos] = tmp.X, cnt[pos] = 1; else if(tmp.X == dp[pos]) cnt[pos]++; } } cout << (cnt[pos] == 0 ? -1: dp[pos]) << "\n"; } }

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

bitaro.cpp: In function 'void prep()':
bitaro.cpp:31:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     if(ptr[from] < gg[from].size() && (mx == -1 || need.X < gg[from][ptr[from]].X))
      |        ~~~~~~~~~~^~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...