| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 525593 |
2022-02-12T05:18:31 Z |
inwbear |
Village (BOI20_village) |
C++14 |
|
2 ms |
2652 KB |
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define MEM(x,a) memset((x),a,sizeof((x)))
#define F first
#define S second
#define imx INT_MAX
const long long MOD = (long long)(1e9+7);
const long long MMX = (long long)(1e18);
typedef long long LL;
typedef pair<int,int> pii;
int n,a,b,h[100005],par[100005][18],wi[100005][18],ans1,Nnum[100005],rr,k,hf,dp[100005],cc,a1[100005],a2[100005];
LL ans2,ans3;
vector<int>v[100005],o;
int dfs(int N,int pr){
bool p=true;
vector<int>mat,nonmat;
dp[N]=1;
Nnum[rr]=N;
rr++;
h[N]=h[pr]+1;
wi[N][0]=1;
par[N][0]=pr;
for(int i=0;i<v[N].size();i++){
if(v[N][i]!=pr){
if(dfs(v[N][i],N)==1)nonmat.pb(v[N][i]);
dp[N]+=dp[v[N][i]];
if(dp[v[N][i]]>hf)p=false;
}
}
if(p){
if(n-dp[N]<=hf)cc=N;
}
if(nonmat.size()>0){
ans1+=nonmat.size()-1;
if(nonmat.size()%2==0){
for(int i=0;i<nonmat.size();i+=2){
a1[nonmat[i]]=nonmat[i+1];
a1[nonmat[i+1]]=nonmat[i];
}
return 1;
}
else{
a1[nonmat[0]]=N;
a1[N]=nonmat[0];
for(int i=1;i<nonmat.size();i+=2){
a1[nonmat[i]]=nonmat[i+1];
a1[nonmat[i+1]]=nonmat[i];
}
return 0;
}
}
else{
return 1;
}
}
void dfs1(int N,int pr){
o.pb(N);
for(int i=0;i<v[N].size();i++){
if(v[N][i]!=pr){
dfs1(v[N][i],N);
}
}
return;
}
void gen_lca(){
for(int i=1;i<18;i++){
for(int j=1;j<=n;j++){
if(par[j][i-1]!=-1){
wi[j][i]=wi[j][i-1]+wi[par[j][i-1]][i-1];
par[j][i]=par[par[j][i-1]][i-1];
}
}
}
return;
}
int lca(int A,int B){
if(h[A]<h[B])swap(A,B);
int diff=h[A]-h[B],re=0;
for(int i=0;i<18;i++){
if((diff>>i)&1){
re+=wi[A][i];
A=par[A][i];
}
}
if(A==B)return re;
for(int i=17;i>=0;i--){
if(par[A][i]!=par[B][i]){
re+=wi[A][i];
re+=wi[B][i];
A=par[A][i];
B=par[B][i];
}
}
re+=wi[A][0]+wi[B][0];
return re;
}
int main(){
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
scanf("%d",&n);
hf=n/2;
ans1=n;
for(int i=1;i<n;i++){
scanf("%d %d",&a,&b);
v[a].pb(b);
v[b].pb(a);
}
for(int i=0;i<18;i++){
for(int j=1;j<=n;j++){
par[j][i]=-1;
}
}
k=dfs(1,0);
ans1+=k;
if(k==1){
a1[1]=a1[v[1][0]];
a1[v[1][0]]=1;
}
gen_lca();
for(int i=1;i<=n;i++){
ans2+=2*lca(i,cc);
}
dfs1(cc,0);
for(int i=0;i<n;i++){
a2[o[i]]=o[n-i-1];
}
printf("%d %lld\n",ans1,ans2);
for(int i=1;i<=n;i++)printf("%d ",a1[i]);
printf("\n");
for(int i=1;i<=n;i++)printf("%d ",a2[i]);
printf("\n");
}
Compilation message
Village.cpp: In function 'int dfs(int, int)':
Village.cpp:25:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
25 | for(int i=0;i<v[N].size();i++){
| ~^~~~~~~~~~~~
Village.cpp:38:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
38 | for(int i=0;i<nonmat.size();i+=2){
| ~^~~~~~~~~~~~~~
Village.cpp:47:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
47 | for(int i=1;i<nonmat.size();i+=2){
| ~^~~~~~~~~~~~~~
Village.cpp: In function 'void dfs1(int, int)':
Village.cpp:60:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
60 | for(int i=0;i<v[N].size();i++){
| ~^~~~~~~~~~~~
Village.cpp: In function 'int main()':
Village.cpp:102:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
102 | scanf("%d",&n);
| ~~~~~^~~~~~~~~
Village.cpp:106:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
106 | scanf("%d %d",&a,&b);
| ~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2636 KB |
Output is correct |
| 2 |
Partially correct |
2 ms |
2636 KB |
Partially correct |
| 3 |
Correct |
2 ms |
2652 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
2636 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2636 KB |
Output is correct |
| 2 |
Partially correct |
2 ms |
2636 KB |
Partially correct |
| 3 |
Correct |
2 ms |
2652 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
2636 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
