oj.uz

Submission #1068645

# Submission time Handle Problem Language Result Execution time Memory
1068645 2024-08-21T11:07:44 Z amirhoseinfar1385 Beech Tree (IOI23_beechtree) C++17
9 / 100
 159 ms 58196 KB 
#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);
}

int calc(int u){
    sz[u]=1;
    int ret=nist[u];
    int cnt=0;
    for(auto x:adj[u]){
        ret|=calc(x);
        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(ret){
        vas[u]=1;
    }
    return ret;
}

bool cmp(int a,int b){
    return (int)adj[a].size()>(int)adj[b].size();
}

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;
    }
    set<int>fst;
    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;
        }
        fst.insert(all[i]);
        st[P[i]].insert(all[i]);
    }
//    for(int i=1;i<=m;i++){
  //      check(i);
    //}
    calc(0);
    sort(adj[0].begin(),adj[0].end(),cmp);
    vector<int>ret(n);
    int f=0;
    for(int i=1;i<(int)adj[0].size();i++){
        for(auto x:st[adj[0][i]]){
            if(st[adj[0][i-1]].count(x)==0){
                f=1;
            }
        }
    }
    if(fst!=st[0]){
        f=1;
    }
    if(f==1){
        vas[0]=1;
    }
    for(int i=0;i<n;i++){
        nist[i]=0;
        ret[i]=(1^vas[i]);
    }
    return ret;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 19032 KB Output is correct
2 Incorrect 3 ms 16988 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
3 Halted 0 ms 0 KB -

Subtask #1
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16988 KB Output is correct
2 Correct 2 ms 16988 KB Output is correct
3 Correct 2 ms 16988 KB Output is correct
4 Correct 3 ms 16988 KB Output is correct
5 Incorrect 3 ms 16988 KB 2nd lines differ - on the 2nd token, expected: '0', found: '1'
6 Halted 0 ms 0 KB -

Subtask #2
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16988 KB Output is correct
2 Correct 2 ms 16988 KB Output is correct
3 Correct 2 ms 16988 KB Output is correct
4 Correct 3 ms 16988 KB Output is correct
5 Incorrect 3 ms 16988 KB 2nd lines differ - on the 2nd token, expected: '0', found: '1'
6 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 19036 KB Output is correct
2 Correct 3 ms 19036 KB Output is correct
3 Correct 3 ms 16988 KB Output is correct
4 Correct 3 ms 16988 KB Output is correct
5 Correct 3 ms 16988 KB Output is correct
6 Correct 4 ms 17020 KB Output is correct
7 Correct 3 ms 16984 KB Output is correct
8 Correct 4 ms 16988 KB Output is correct
9 Correct 3 ms 16832 KB Output is correct
10 Correct 3 ms 16988 KB Output is correct
11 Correct 3 ms 16988 KB Output is correct
12 Correct 3 ms 16988 KB Output is correct
13 Correct 3 ms 16988 KB Output is correct
14 Correct 3 ms 17036 KB Output is correct
15 Correct 51 ms 25168 KB Output is correct
16 Correct 50 ms 24660 KB Output is correct
17 Correct 49 ms 24912 KB Output is correct
18 Correct 47 ms 25172 KB Output is correct

Subtask #4
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16988 KB Output is correct
2 Correct 2 ms 16988 KB Output is correct
3 Correct 3 ms 19032 KB Output is correct
4 Correct 2 ms 16988 KB Output is correct
5 Incorrect 159 ms 58196 KB 2nd lines differ - on the 2nd token, expected: '0', found: '1'
6 Halted 0 ms 0 KB -

Subtask #5
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 19032 KB Output is correct
2 Incorrect 3 ms 16988 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
3 Halted 0 ms 0 KB -

Subtask #6
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16988 KB Output is correct
2 Correct 2 ms 16988 KB Output is correct
3 Correct 3 ms 19032 KB Output is correct
4 Correct 2 ms 16988 KB Output is correct
5 Incorrect 3 ms 16984 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
6 Halted 0 ms 0 KB -

Subtask #7
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 19032 KB Output is correct
2 Incorrect 3 ms 16988 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
3 Halted 0 ms 0 KB -

Subtask #8
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16988 KB Output is correct
2 Correct 2 ms 16988 KB Output is correct
3 Correct 3 ms 19032 KB Output is correct
4 Correct 2 ms 16988 KB Output is correct
5 Incorrect 3 ms 16984 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
6 Halted 0 ms 0 KB -

Subtask #9
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 19032 KB Output is correct
2 Incorrect 3 ms 16988 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
3 Halted 0 ms 0 KB -