답안 #1068763

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1068763	2024-08-21T11:54:11 Z	amirhoseinfar1385	참나무 (IOI23_beechtree)	C++17	17 / 100	121 ms	78804 KB

beechtree

#include "beechtree.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=200000+10;
int n,m,all[maxn],dp[maxn],vas[maxn],nist[maxn],sz[maxn],tof[maxn];
set<int>st[maxn];
vector<int>adj[maxn];
 
int dfsch2(int u){
    int ret=dp[u];
    for(auto x:adj[u]){
        int fake=dfsch2(x);
        if(fake==1&&dp[u]==0){
      //      if(u==2){
        //        cout<<"wtf"<<endl;
          //  }
            nist[u]=1;
            ret|=fake;
        }
    }
    return ret;
}
 
void check(int cl){
    for(int j=0;j<n;j++){
        dp[j]=st[j].count(cl);
    }
    dfsch2(0);
}
bool cmp(int a,int b){
    return (int)adj[a].size()>(int)adj[b].size();
}
int high[maxn];

int calc(int u){
    sz[u]=1;
    int ret=nist[u];
    int cnt=0;
    high[u]=1;
    for(auto x:adj[u]){
        ret|=calc(x);
        high[u]=max(high[u],high[x]+1);
        sz[u]+=sz[x];
     /*   if(sz[x]>1){
            cnt++;
            tof[u]=all[x];
            if(tof[x]!=-1&&tof[x]!=tof[u]){
                ret=1;
            }
        }*/
    }
    if(cnt>1){
        ret=1;
    }
    if(high[u]>3){
        vas[u]=1;
        return 1;
    }
    if(high[u]<=2){
        if(nist[u]){
            vas[u]=1;
        }
        return vas[u];
    }
    set<int>fst;
    for(auto x:adj[u]){
        for(auto y:st[x]){
            fst.insert(y);
        }
    }
    for(auto y:st[u]){
        fst.insert(y);
    }
    sort(adj[u].begin(),adj[u].end(),cmp);
    int f=0;
    for(int i=1;i<(int)adj[u].size();i++){
        for(auto x:st[adj[u][i]]){
            if(st[adj[u][i-1]].count(x)==0){
                f=1;
            }
        }
    }
    if(fst!=st[u]){
        f=1;
    }
    if(f==1){
        vas[u]=1;
    }

    if(ret){
        vas[u]=1;
    }
    if(vas[u]){
        ret=1;
    }
    return ret;
}
 



std::vector<int> beechtree(int N, int M, std::vector<int> P, std::vector<int> C)
{
    n=N;
    m=M;
    for(int i=0;i<n;i++){
        tof[i]=-1;
    }
    for(int i=1;i<=n-1;i++){
        adj[P[i]].push_back(i);
        all[i]=C[i];
        if(st[P[i]].count(all[i])!=0){
            nist[P[i]]=1;
        }
        st[P[i]].insert(all[i]);
    }
    calc(0);
    vector<int>ret(n);
    for(int i=0;i<n;i++){
        nist[i]=0;
        ret[i]=(1^vas[i]);
    }
    return ret;
}

Subtask #0
0.0 / 0.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	14428 KB	Output is correct
2	Correct	6 ms	14448 KB	Output is correct
3	Correct	6 ms	14428 KB	Output is correct

Subtask #1
0.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	14424 KB	Output is correct
2	Correct	6 ms	14428 KB	Output is correct
3	Incorrect	7 ms	14428 KB	2nd lines differ - on the 1st token, expected: '1', found: '0'
4	Halted	0 ms	0 KB	-

Subtask #2
0.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	14424 KB	Output is correct
2	Correct	6 ms	14428 KB	Output is correct
3	Incorrect	7 ms	14428 KB	2nd lines differ - on the 1st token, expected: '1', found: '0'
4	Halted	0 ms	0 KB	-

Subtask #3
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	14428 KB	Output is correct
2	Correct	6 ms	14428 KB	Output is correct
3	Correct	5 ms	14528 KB	Output is correct
4	Correct	5 ms	14532 KB	Output is correct
5	Correct	6 ms	14424 KB	Output is correct
6	Correct	6 ms	14528 KB	Output is correct
7	Correct	6 ms	14428 KB	Output is correct
8	Correct	6 ms	14544 KB	Output is correct
9	Correct	6 ms	14428 KB	Output is correct
10	Correct	5 ms	14428 KB	Output is correct
11	Correct	7 ms	14424 KB	Output is correct
12	Correct	7 ms	14428 KB	Output is correct
13	Correct	6 ms	14424 KB	Output is correct
14	Correct	6 ms	14428 KB	Output is correct
15	Correct	55 ms	24952 KB	Output is correct
16	Correct	53 ms	24384 KB	Output is correct
17	Correct	54 ms	24400 KB	Output is correct
18	Correct	57 ms	24916 KB	Output is correct

Subtask #4
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	14424 KB	Output is correct
2	Correct	6 ms	14428 KB	Output is correct
3	Correct	5 ms	14428 KB	Output is correct
4	Correct	5 ms	14428 KB	Output is correct
5	Correct	91 ms	78676 KB	Output is correct
6	Correct	96 ms	78804 KB	Output is correct
7	Correct	5 ms	14428 KB	Output is correct
8	Correct	5 ms	14428 KB	Output is correct
9	Correct	6 ms	14632 KB	Output is correct
10	Correct	7 ms	14740 KB	Output is correct
11	Correct	88 ms	38748 KB	Output is correct
12	Correct	121 ms	33876 KB	Output is correct

Subtask #5
0.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	14428 KB	Output is correct
2	Correct	6 ms	14448 KB	Output is correct
3	Correct	6 ms	14428 KB	Output is correct
4	Correct	6 ms	14424 KB	Output is correct
5	Correct	6 ms	14428 KB	Output is correct
6	Incorrect	7 ms	14428 KB	2nd lines differ - on the 1st token, expected: '1', found: '0'
7	Halted	0 ms	0 KB	-

Subtask #6
0.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	14424 KB	Output is correct
2	Correct	6 ms	14428 KB	Output is correct
3	Correct	5 ms	14428 KB	Output is correct
4	Correct	5 ms	14428 KB	Output is correct
5	Correct	7 ms	14540 KB	Output is correct
6	Correct	7 ms	14552 KB	Output is correct
7	Correct	6 ms	14428 KB	Output is correct
8	Correct	7 ms	14344 KB	Output is correct
9	Correct	5 ms	14428 KB	Output is correct
10	Correct	5 ms	14424 KB	Output is correct
11	Correct	6 ms	14428 KB	Output is correct
12	Correct	5 ms	14372 KB	Output is correct
13	Correct	5 ms	14424 KB	Output is correct
14	Correct	6 ms	14428 KB	Output is correct
15	Correct	5 ms	14428 KB	Output is correct
16	Incorrect	5 ms	14428 KB	2nd lines differ - on the 1st token, expected: '1', found: '0'
17	Halted	0 ms	0 KB	-

Subtask #7
0.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	14428 KB	Output is correct
2	Correct	6 ms	14448 KB	Output is correct
3	Correct	6 ms	14428 KB	Output is correct
4	Correct	6 ms	14424 KB	Output is correct
5	Correct	6 ms	14428 KB	Output is correct
6	Incorrect	7 ms	14428 KB	2nd lines differ - on the 1st token, expected: '1', found: '0'
7	Halted	0 ms	0 KB	-

Subtask #8
0.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	14424 KB	Output is correct
2	Correct	6 ms	14428 KB	Output is correct
3	Correct	5 ms	14428 KB	Output is correct
4	Correct	5 ms	14428 KB	Output is correct
5	Correct	7 ms	14540 KB	Output is correct
6	Correct	7 ms	14552 KB	Output is correct
7	Correct	6 ms	14428 KB	Output is correct
8	Correct	7 ms	14344 KB	Output is correct
9	Correct	5 ms	14428 KB	Output is correct
10	Correct	5 ms	14424 KB	Output is correct
11	Correct	6 ms	14428 KB	Output is correct
12	Correct	5 ms	14372 KB	Output is correct
13	Correct	5 ms	14424 KB	Output is correct
14	Correct	6 ms	14428 KB	Output is correct
15	Correct	5 ms	14428 KB	Output is correct
16	Incorrect	5 ms	14428 KB	2nd lines differ - on the 1st token, expected: '1', found: '0'
17	Halted	0 ms	0 KB	-

Subtask #9
0.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	14428 KB	Output is correct
2	Correct	6 ms	14448 KB	Output is correct
3	Correct	6 ms	14428 KB	Output is correct
4	Correct	6 ms	14424 KB	Output is correct
5	Correct	6 ms	14428 KB	Output is correct
6	Incorrect	7 ms	14428 KB	2nd lines differ - on the 1st token, expected: '1', found: '0'
7	Halted	0 ms	0 KB	-

답안 #1068763

Compilation message