제출 #396129

#제출 시각아이디문제언어결과실행 시간메모리
396129pure_memBitaro’s Party (JOI18_bitaro)C++14
0 / 100
3 ms4940 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 = 1e5 + 1, BS = 300; const ll INF = 1e18; int n, m, q, used[N], dp[N]; vector< int > g[N]; vector< pair<int, int> > gg[N]; int main () { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); cin >> n >> m >> q; for(int i = 1, x, y;i <= y;i++){ cin >> x >> y; g[y].push_back(x); } set< pair<int, int> > act; for(int i = 2;i <= n;i++){ act.clear(); for(int from: g[i]){ if(used[from] != i) used[from] = i, dp[from] = 1, act.insert(MP(1, from)); for(pair<int, int> tmp: gg[from]){ if(used[tmp.Y] != i) dp[tmp.Y] = 0, used[tmp.Y] = i; if(tmp.X + 1 > dp[tmp.Y]){ act.erase(MP(dp[tmp.Y], tmp.Y)); dp[tmp.Y] = tmp.X + 1; act.insert(MP(dp[tmp.Y], tmp.Y)); if(act.size() > BS) used[act.begin()->Y] = -1, act.erase(act.begin()); } } while(!act.empty()){ gg[i].push_back(*act.begin()); act.erase(act.begin()); } } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...