Submission #583690

#TimeUTC-0UsernameProblemLanguageResultExecution timeMemory
5836902022-06-26 05:00:56joelauSplit the Attractions (IOI19_split)C++14
0 / 100
1002 ms1048576 KiB
#include "split.h"
#include <bits/stdc++.h>
using namespace std;
int N,M,A,B,C, dist[100005];
vector<int> lst[100005], ans;
pair<int,int> tmp[3];
queue<int> Q;
void dfs (int x, int p, int d) {
dist[x] = d;
for (int v: lst[x]) if (v != p) dfs(v,x,d+1);
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
N = n, M = p.size(), A = a, B = b, C = c;
for (int i = 0; i < M; ++i) lst[p[i]].push_back(q[i]), lst[q[i]].push_back(p[i]);
dfs(0,-1,0);
pair<int,int> S = make_pair(-1,-1);
for (int i = 0; i < N; ++i) S = max(S,make_pair(dist[i],i));
dfs(S.second,-1,0);
pair<int,int> T = make_pair(-1,-1);
for (int i = 0; i < N; ++i) T = max(T,make_pair(dist[i],i));
tmp[0] = make_pair(A,1), tmp[1] = make_pair(B,2), tmp[2] = make_pair(C,3);
sort(tmp,tmp+3);
ans.assign(N,tmp[2].second);
Q.push(S.second);
ans[S.second] = tmp[0].second;
int cnt = 1;
while (!Q.empty() && cnt < tmp[0].first) {
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...