結果
問題 | No.1024 Children in a Row |
ユーザー |
|
提出日時 | 2020-04-10 23:17:30 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 737 ms / 2,000 ms |
コード長 | 1,761 bytes |
コンパイル時間 | 4,563 ms |
コンパイル使用メモリ | 198,220 KB |
最終ジャッジ日時 | 2025-01-09 16:53:07 |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 27 |
ソースコード
#include <bits/stdc++.h> using namespace std; int main(){ int N, M; cin >> N >> M; static vector<int> edges[400000]; vector<int> V(N+M); vector<int> active(N), bef(N+M); vector<int> K(N+M); for(int i=0; i<N; i++){ V[i] = i; active[i] = i; if(i) edges[i-1].push_back(i); } for(int i=N; i<N+M; i++){ int a, b, k; cin >> a >> b >> k; a--; b--; k--; K[i] = k; edges[active[b]].push_back(i); V[i] = a; bef[i] = active[a]; active[a] = i; } for(int i=0; i<N+M; i++) reverse(edges[i].begin(), edges[i].end()); vector<int> order; vector<int> subnum(N+M), pos(N+M); auto dfs = [&](auto&& dfs, int i)->int{ int res = 0; pos[i] = order.size(); if(active[V[i]] == i){ order.push_back(V[i]); res++; } for(int j : edges[i]) res += dfs(dfs, j); subnum[i] = res; return res; }; dfs(dfs, 0); for(int i=N; i<N+M; i++){ int posbef = pos[bef[i]]; int posaft = pos[i]; int num = subnum[i]; int ans = 0; if(K[i] < min(posbef, posaft) || K[i] >= max(posbef, posaft+num)){ ans = order[K[i]]; }else if(posbef <= posaft){ int R = K[i] - posbef; if(R < num){ ans = order[posaft+R]; }else{ ans = order[K[i]-num]; } }else{ int R = K[i] - posaft; int mid = posbef-posaft-num; if(R < mid){ ans = order[K[i]+num]; }else{ ans = order[posaft+R-mid]; } } cout << ans+1 << endl; } return 0; }