結果
問題 | 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;}