結果
問題 | No.1817 Reversed Edges |
ユーザー | ytft |
提出日時 | 2022-02-13 21:07:35 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 729 ms / 2,000 ms |
コード長 | 2,309 bytes |
コンパイル時間 | 3,587 ms |
コンパイル使用メモリ | 272,804 KB |
実行使用メモリ | 32,100 KB |
最終ジャッジ日時 | 2023-09-11 15:40:38 |
合計ジャッジ時間 | 16,045 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,380 KB |
testcase_01 | AC | 1 ms
4,376 KB |
testcase_02 | AC | 2 ms
4,380 KB |
testcase_03 | AC | 1 ms
4,380 KB |
testcase_04 | AC | 2 ms
4,376 KB |
testcase_05 | AC | 1 ms
4,380 KB |
testcase_06 | AC | 1 ms
4,380 KB |
testcase_07 | AC | 607 ms
28,188 KB |
testcase_08 | AC | 226 ms
15,372 KB |
testcase_09 | AC | 538 ms
26,960 KB |
testcase_10 | AC | 280 ms
17,084 KB |
testcase_11 | AC | 384 ms
20,972 KB |
testcase_12 | AC | 726 ms
31,868 KB |
testcase_13 | AC | 695 ms
31,624 KB |
testcase_14 | AC | 698 ms
31,736 KB |
testcase_15 | AC | 707 ms
31,864 KB |
testcase_16 | AC | 708 ms
31,680 KB |
testcase_17 | AC | 686 ms
31,536 KB |
testcase_18 | AC | 696 ms
31,676 KB |
testcase_19 | AC | 710 ms
31,560 KB |
testcase_20 | AC | 711 ms
31,556 KB |
testcase_21 | AC | 729 ms
31,676 KB |
testcase_22 | AC | 381 ms
32,100 KB |
testcase_23 | AC | 378 ms
32,000 KB |
testcase_24 | AC | 408 ms
31,508 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; struct tree{ vector<int> parent; int numberOfNodes=0; int root; tree(int N,vector<int>& a,int k=0){ parent=a; numberOfNodes=N; root=k; } tree(int N,set<vector<int>>& edges,int k=0){ root=k; numberOfNodes=N; parent.resize(N); fill(parent.begin(),parent.end(),-1); map<int,set<int>> connected; for(vector<int> v:edges){ connected[v[0]].insert(v[1]); connected[v[1]].insert(v[0]); } queue<int> q; q.push(k); while(!q.empty()){ for(int i:connected[q.front()]){ if(i!=k&&parent[i]==-1){ parent[i]=q.front(); q.push(i); } } q.pop(); } } map<int,vector<int>> getChildren(){ map<int,vector<int>> ret; for(int i=0;i<numberOfNodes;++i){ if(i!=root){ ret[parent[i]].emplace_back(i); } } return ret; } vector<int> bfs(){ vector<int> order(1,root); map<int,vector<int>> children=getChildren(); for(int i=0;i<numberOfNodes;++i){ for(int j:children[order[i]]){ order.emplace_back(j); } } return order; } vector<int> getDepth(){ vector<int> depth(numberOfNodes); vector<int> order=bfs(); depth[root]=0; for(int i=1;i<numberOfNodes;++i){ depth[order[i]]=depth[parent[order[i]]]+1; } return depth; } }; int main(){ int N; cin>>N; set<vector<int>> edges; for(int i=0;i<N-1;++i){ vector<int> temp(2); for(int j=0;j<2;++j){ cin>>temp[j]; --temp[j]; } edges.insert(temp); } tree T(N,edges,0); vector<int> d=T.getDepth(),ans(N,0),ord=T.bfs(); for(vector<int> v:edges){ if(d[max(v[0],v[1])]<d[min(v[0],v[1])]){ ++ans[0]; --ans[min(v[0],v[1])]; }else{ ++ans[max(v[0],v[1])]; } } for(int i:ord){ if(i){ ans[i]+=ans[T.parent[i]]; } } for(int i=0;i<N;++i){ cout<<ans[i]<<endl; } }