結果
問題 | No.1254 補強への架け橋 |
ユーザー |
![]() |
提出日時 | 2020-10-23 15:27:14 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 77 ms / 2,000 ms |
コード長 | 1,517 bytes |
コンパイル時間 | 835 ms |
コンパイル使用メモリ | 97,416 KB |
実行使用メモリ | 10,692 KB |
最終ジャッジ日時 | 2024-07-21 10:05:24 |
合計ジャッジ時間 | 12,189 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 123 |
ソースコード
/* -*- coding: utf-8 -*- * * 1254.cc: No.1254 補強への架け橋 - yukicoder */ #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<iostream> #include<string> #include<vector> #include<map> #include<set> #include<stack> #include<list> #include<queue> #include<deque> #include<algorithm> #include<numeric> #include<utility> #include<complex> #include<functional> using namespace std; /* constant */ const int MAX_N = 100000; /* typedef */ typedef pair<int,int> pii; typedef vector<pii> vpii; /* global variables */ vpii nbrs[MAX_N]; int ps[MAX_N], ds[MAX_N], cis[MAX_N]; int es[MAX_N]; /* subroutines */ /* main */ int main() { int n; scanf("%d", &n); for (int i = 0; i < n; i++) { int a, b; scanf("%d%d", &a, &b); a--, b--; nbrs[a].push_back(pii(b, i)); nbrs[b].push_back(pii(a, i)); } memset(ds, -1, sizeof(ds)); ps[0] = -1, ds[0] = 1; int l = -1, r = -1; for (int u = 0; u >= 0;) { if (cis[u] < nbrs[u].size() && nbrs[u][cis[u]].first == ps[u]) cis[u]++; if (cis[u] < nbrs[u].size()) { pii a = nbrs[u][cis[u]++]; int v = a.first, ei = a.second; es[ds[u]] = ei; if (ds[v] < 0) { ps[v] = u, ds[v] = ds[u] + 1; u = v; } else { l = ds[v], r = ds[u] + 1; break; } } else u = ps[u]; } //printf("l=%d, r=%d\n", l, r); printf("%d\n", r - l); for (int i = l; i < r; i++) { printf("%d", es[i] + 1); putchar(i + 1 < r ? ' ' : '\n'); } return 0; }