이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "fun.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+5;
int N,root,depth[maxn];
int odakle;
vector<int> R,koji[5];
vector<int> V;
bool podub(int a,int b){
return depth[a]<depth[b];
}
void findroot(){
root=1;
for(int i=2;i<=N;i++)
if(attractionsBehind(root-1,i-1)>=(N+1)/2)
root=i;
return;
}
void finddepth(){
for(int i=1;i<=N;i++){
depth[i]=hoursRequired(root-1,i-1);
// cout<<i<<" dubina "<<depth[i]<<endl;
if(depth[i]==1)
R.push_back(i);
}
return;
}
bool insubtree(int a,int b){
//cout<<a<<" "<<b<<" "<<attractionsBehind(a-1,b-1)<<endl;
return attractionsBehind(a-1,b-1)>=(N+1)/2;
}
void findsubtree(){
for(int i=1;i<=N;i++){
if(depth[i]==0)
continue;
if(insubtree(i,R[0]))
koji[0].push_back(i);
else if(insubtree(i,R[1]))
koji[1].push_back(i);
else
koji[2].push_back(i);
}
}
int dist(int a,int b){
return depth[a]+depth[b];
}
void dodaj(int idx){
if(koji[idx].size()==0)
return;
odakle=idx;
//cout<<idx<<" "<<koji[idx].back()<<endl;
V.push_back(koji[idx].back());
koji[idx].pop_back();
return;
}
void spoj(int a,int b){
int c=a^b^3;
if(dist(V.back(),koji[c].back())<dist(koji[c].back(),koji[3^c^odakle].back()))
dodaj(3^odakle^c);
if(a>b)
swap(a,b);
for(int i=0;i<koji[b].size();i++)
koji[a].push_back(koji[b][i]);
sort(koji[a].begin(),koji[a].end(),podub);
if(b==1){
koji[1]=koji[2];
if(odakle==2)
odakle=1;
}
koji[2].clear();
if(odakle==b)
odakle=a;
}
vector<int> createFunTour(int n, int Q) {
N=n;
findroot();
//cout<<"ROOT JE "<<root<<endl;
finddepth();
findsubtree();
for(int i=0;i<=2;i++)
if(koji[i].size())
sort(koji[i].begin(),koji[i].end(),podub);
// cout<<koji[0].size()<<" "<<koji[1].size()<<" "<<koji[2].size()<<endl;
if(koji[0].size()>=koji[1].size() and koji[0].size()>=koji[2].size())
dodaj(0);
else if(koji[1].size()>=koji[0].size() and koji[1].size()>=koji[2].size())
dodaj(1);
else
dodaj(2);
while(koji[2].size()){
//cout<<koji[0].size()<<" "<<koji[1].size()<<" "<<koji[2].size()<<endl;
if(koji[0].size()+koji[1].size()==koji[2].size()){
spoj(0,1);
break;
}
if(koji[0].size()+koji[2].size()==koji[1].size()){
spoj(0,2);
break;
}
if(koji[1].size()+koji[2].size()==koji[0].size()){
spoj(1,2);
break;
}
int nd=0;
if(odakle==0)
nd=1;
for(int i=1;i<=2;i++)
if(depth[koji[i].back()]>depth[koji[nd].back()] and i!=odakle)
nd=i;
dodaj(nd);
}
//cout<<odakle<<endl;
//cout<<koji[0].size()<<" "<<koji[1].size()<<" "<<koji[2].size()<<endl;
for(int it=1;it<=N;it++)
dodaj(odakle^1);
while(koji[0].size()){
V.push_back(koji[0].back());
koji[0].pop_back();
}
while(koji[1].size()){
V.push_back(koji[1].back());
koji[1].pop_back();
}
//cout<<"ROOT JE "<<root<<endl;
V.push_back(root);
for(int i=0;i<V.size();i++)
V[i]--;
return V;
}
/*
7 400000
0 1
0 5
0 6
1 2
1 4
2 3
*/
컴파일 시 표준 에러 (stderr) 메시지
fun.cpp: In function 'void spoj(int, int)':
fun.cpp:63:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
63 | for(int i=0;i<koji[b].size();i++)
| ~^~~~~~~~~~~~~~~
fun.cpp: In function 'std::vector<int> createFunTour(int, int)':
fun.cpp:127:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
127 | for(int i=0;i<V.size();i++)
| ~^~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |