QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#367624 | #2369. Joint Excavation | kevinyang# | RE | 4ms | 14556kb | C++17 | 2.1kb | 2024-03-26 10:52:48 | 2024-03-26 10:52:49 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mxn = 200005;
vector<vector<int>>g(mxn);
vector<vector<int>>adj(mxn);
vector<bool>vis(mxn);
vector<int>sz(mxn);
set<int>leftv;
vector<int>ans;
int rq = 0;
void dfs(int u){
sz[u] = 1;
for(int nxt: adj[u]){
if(vis[nxt])continue;
g[u].push_back(nxt);
vis[nxt] = true;
dfs(nxt);
sz[u]+=sz[nxt];
}
}
set<int> get(int u, int p){
set<int>s;
s.insert(u);
for(int nxt: g[u]){
set<int>t = get(nxt,u);
if(s.size()<t.size()){
swap(s,t);
}
for(int nxt: t){
s.insert(nxt);
}
}
return s;
}
void dfs1(int u, int p){
if(rq == sz[u]*2){
for(int nxt: get(u, p)){
leftv.insert(nxt);
}
return;
}
rq--;
ans.push_back(u);
vector<pair<int,int>>vals;
for(int nxt: g[u]){
vals.push_back({sz[nxt],nxt});
}
sort(vals.begin(),vals.end());
for(auto [_, nxt]: vals){
if(rq >= sz[nxt]*2){
//cout << "found " << '\n';
rq-=sz[nxt]*2;
for(int node: get(nxt, p)){
//cout << "get " << nxt << '\n';
leftv.insert(node);
}
if(rq==0)return;
continue;
}
dfs1(nxt, u);
return;
}
}
signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
vis[1] = true;
int n,m;
cin >> n >> m;
for(int i = 0; i<m; i++){
int x,y;
cin >> x >> y;
adj[x].push_back(y);
adj[y].push_back(x);
}
rq = n;
dfs(1);
dfs1(1,0);
cout << ans.size() << ' ' << (n-ans.size())/2 << '\n';
set<int>right;
for(int i = 1; i<=n; i++){
right.insert(i);
}
for(int i = 0; i<ans.size(); i++){
right.erase(ans[i]);
cout << ans[i];
if(i+1<ans.size())cout << ' ';
}
for(int nxt: leftv){
right.erase(nxt);
}
cout << '\n';
assert(leftv.size() == right.size());
if((n-ans.size())/2){
vector<int>vec;
for(int nxt: leftv){
vec.push_back(nxt);
}
for(int i = 0; i<vec.size(); i++){
cout << vec[i];
if(i+1<vec.size())cout << ' ';
}
cout << '\n';
vec.clear();
for(int nxt: right){
vec.push_back(nxt);
}
for(int i = 0; i<vec.size(); i++){
cout << vec[i];
if(i+1<vec.size())cout << ' ';
}
cout << '\n';
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 14036kb
input:
1 0
output:
1 0 1
result:
ok
Test #2:
score: 0
Accepted
time: 0ms
memory: 13940kb
input:
20 25 17 14 5 14 3 18 14 2 13 4 18 8 18 20 2 20 2 1 2 19 2 10 4 10 4 15 20 1 20 19 20 10 10 1 10 19 1 19 1 6 19 9 6 11 6 12 9 16 9 7
output:
4 8 1 2 20 18 3 5 6 8 11 12 14 17 4 7 9 10 13 15 16 19
result:
ok
Test #3:
score: 0
Accepted
time: 3ms
memory: 13952kb
input:
20 22 19 6 11 6 2 6 6 15 15 13 13 12 12 7 7 15 15 12 7 13 3 14 8 14 20 14 14 13 12 5 5 18 5 9 5 4 7 16 16 17 16 10 16 1
output:
6 7 1 16 7 12 13 14 3 4 5 9 10 17 18 2 6 8 11 15 19 20
result:
ok
Test #4:
score: 0
Accepted
time: 0ms
memory: 14292kb
input:
63 119 48 45 45 41 15 58 23 43 18 42 41 1 33 20 26 6 18 12 34 17 5 24 2 61 62 11 16 27 6 14 39 47 39 19 29 52 22 41 33 36 31 28 10 28 2 32 54 56 32 45 57 25 51 26 7 32 43 58 1 25 9 58 3 40 53 12 41 46 6 3 37 15 24 4 54 4 41 25 7 45 5 4 48 63 30 13 36 19 44 13 3 18 19 29 62 17 32 61 47 34 32 44 2 8 5...
output:
29 17 1 41 45 48 63 61 2 32 7 25 57 17 34 47 39 19 36 21 26 6 3 40 13 30 24 5 4 54 56 8 11 14 20 22 29 33 35 44 46 49 51 52 55 59 60 62 9 10 12 15 16 18 23 27 28 31 37 38 42 43 50 53 58
result:
ok
Test #5:
score: 0
Accepted
time: 4ms
memory: 14556kb
input:
1000 3000 769 860 860 945 945 136 136 665 665 266 266 549 549 917 917 404 404 591 591 336 336 749 749 17 17 129 129 870 870 472 591 126 126 740 740 397 397 894 894 582 582 939 939 22 22 947 947 21 21 277 277 607 607 538 538 634 634 154 154 220 220 615 21 455 455 202 202 47 47 748 748 620 620 367 367...
output:
718 141 1 792 566 324 722 499 443 71 367 620 748 47 202 455 21 947 22 939 582 894 397 740 126 591 404 917 549 266 665 136 945 860 769 332 959 606 848 942 288 221 918 632 461 762 544 564 439 709 154 634 538 607 277 613 162 532 569 64 673 755 602 605 417 868 624 680 237 333 736 790 548 562 210 77 819 ...
result:
ok
Test #6:
score: -100
Runtime Error
input:
1000 4000 464 484 484 988 988 735 735 247 247 269 269 16 16 46 46 40 40 543 543 236 236 107 107 660 660 58 58 270 270 705 705 161 161 797 797 444 444 395 395 710 710 488 488 162 162 202 202 353 353 430 430 804 804 371 371 47 47 819 819 566 566 92 270 275 275 860 860 208 208 704 704 580 580 317 317 6...