oj.uz

답안 #1061810

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1061810 2024-08-16T13:47:41 Z noyancanturk 참나무 (IOI23_beechtree) C++17
22 / 100
 220 ms 180132 KB 
#include "beechtree.h"

#include <bits/stdc++.h>
using namespace std;

const int lim=2e5+100;

using pii=pair<int,int>;

#define pb push_back

int n,m;
vector<int>p,c;
int dep[lim];
vector<int>v[lim];
unordered_map<int,int>guycnt[lim],col[lim];
map<int,int>cnt[lim];

struct Node{
    int dep=0,chcnt=0,minch=0,maxch=0;
}dat[lim];

using pnode=Node*;

struct cmp{
    bool operator()(pnode i,pnode j) const {
        if(i->dep^j->dep)return i->dep<j->dep;
        if(i->chcnt^j->chcnt)return i->chcnt>j->chcnt;
        if(i->minch^j->minch)return i->minch>j->minch;
        return i->maxch>j->maxch;
    }
};

set<pnode,cmp>ct[lim];

bool insertnode(int par,pnode x){
    auto p=ct[par].insert(x).first;
    if(p!=ct[par].begin()){
        auto pp=prev(p);
        if((*pp)->chcnt<x->chcnt)return 0;
        if((*pp)->minch<x->minch)return 0;
        if((*pp)->maxch<x->maxch)return 0;
    }
    auto pp=next(p);
    if(pp!=ct[par].end()){
        if((*pp)->chcnt>x->chcnt)return 0;
        if((*pp)->minch>x->minch)return 0;
        if((*pp)->maxch>x->maxch)return 0;
    }
    return 1;
}

vector<int>dp;

void dfs(int node){
    for(int j:v[node]){
        dfs(j);
        if(!dp[j]){
            dp[node]=0;
        }
    }
    if(!dp[node])return;
    insertnode(node,dat+node);
    for(int j:v[node]){
        if(ct[node].size()<ct[j].size()){
            swap(ct[j],ct[node]);
        }
        for(pnode p:ct[j]){
            if(!insertnode(node,p)){
                dp[node]=0;
                return;
            }
        }
        if(col[node].size()<col[j].size()){
            swap(col[node],col[j]);
            swap(cnt[node],cnt[j]);
        }
        for(auto[x,y]:col[j]){
            if((--cnt[node][col[node][x]])==0){
                cnt[node].erase(col[node][x]);
            }
            cnt[node][col[node][x]+=y]++;
        }
        if(guycnt[node].size()<guycnt[j].size()){
            swap(guycnt[j],guycnt[node]);
        }
        for(auto[x,y]:guycnt[j]){
            guycnt[node][x]+=y;
        }
    }
    int have=col[node].size(),prevsum=0;
    for(auto[x,y]:cnt[node]){
        if(guycnt[node][have]!=x-prevsum){
            dp[node]=0;
            return;
        }
        have-=y;
        prevsum=x;
    }
}

std::vector<int> beechtree(int N, int M, std::vector<int> P, std::vector<int> C){
    n=N,m=M;
    p=P,c=C;
    dp=vector<int>(n,1);
    for(int i=1;i<n;i++){
        v[P[i]].pb(i);
        if(col[P[i]].count(C[i]))dp[P[i]]=0;
        col[P[i]][c[i]]=1;
        cnt[p[i]][1]++;
    }
    for(int i=n-1;0<=i;i--){
        guycnt[i][v[i].size()]++;;
        dat[i].chcnt=v[i].size();
        if(dat[i].chcnt){
            dat[i].minch=INT_MAX;
            dat[i].maxch=0;
            for(int j:v[i]){
                dat[i].minch=min(dat[i].minch,dat[j].chcnt);
                dat[i].maxch=max(dat[i].maxch,dat[j].chcnt);
            }
        }
    }
    for(int i=1;i<n;i++){
        dep[i]=dep[p[i]]+1;
    }
    dfs(0);
    return dp;
}

Subtask #0
0.0 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 47192 KB Output is correct
2 Correct 8 ms 46940 KB Output is correct
3 Correct 9 ms 46940 KB Output is correct

Subtask #1
0.0 / 9.0

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

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 46936 KB Output is correct
2 Correct 8 ms 46940 KB Output is correct
3 Correct 7 ms 46940 KB Output is correct
4 Correct 9 ms 46940 KB Output is correct
5 Correct 9 ms 46940 KB Output is correct
6 Correct 7 ms 46940 KB Output is correct
7 Correct 201 ms 171092 KB Output is correct
8 Correct 213 ms 171092 KB Output is correct
9 Correct 9 ms 46936 KB Output is correct
10 Correct 8 ms 46940 KB Output is correct
11 Correct 8 ms 46940 KB Output is correct
12 Correct 8 ms 46940 KB Output is correct
13 Correct 9 ms 48220 KB Output is correct
14 Correct 10 ms 48220 KB Output is correct
15 Correct 11 ms 47984 KB Output is correct
16 Correct 10 ms 47960 KB Output is correct
17 Correct 194 ms 180132 KB Output is correct
18 Correct 220 ms 177264 KB Output is correct
19 Correct 215 ms 172624 KB Output is correct
20 Correct 174 ms 171088 KB Output is correct

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 46940 KB Output is correct
2 Correct 8 ms 46940 KB Output is correct
3 Correct 8 ms 46940 KB Output is correct
4 Correct 8 ms 46940 KB Output is correct
5 Correct 9 ms 47196 KB Output is correct
6 Correct 8 ms 46940 KB Output is correct
7 Correct 7 ms 46940 KB Output is correct
8 Correct 9 ms 46940 KB Output is correct
9 Correct 8 ms 46944 KB Output is correct
10 Correct 8 ms 46936 KB Output is correct
11 Correct 9 ms 47196 KB Output is correct
12 Correct 8 ms 47192 KB Output is correct
13 Correct 8 ms 47196 KB Output is correct
14 Correct 9 ms 47204 KB Output is correct
15 Correct 85 ms 78136 KB Output is correct
16 Correct 80 ms 76536 KB Output is correct
17 Correct 65 ms 76880 KB Output is correct
18 Correct 76 ms 77652 KB Output is correct

Subtask #4
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 46936 KB Output is correct
2 Correct 8 ms 46940 KB Output is correct
3 Correct 8 ms 46940 KB Output is correct
4 Correct 8 ms 46940 KB Output is correct
5 Correct 201 ms 171092 KB Output is correct
6 Correct 213 ms 171092 KB Output is correct
7 Correct 9 ms 46936 KB Output is correct
8 Correct 8 ms 46940 KB Output is correct
9 Correct 9 ms 47440 KB Output is correct
10 Correct 9 ms 47452 KB Output is correct
11 Correct 188 ms 116960 KB Output is correct
12 Correct 144 ms 101116 KB Output is correct

Subtask #5
0.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 47192 KB Output is correct
2 Correct 8 ms 46940 KB Output is correct
3 Correct 9 ms 46940 KB Output is correct
4 Correct 8 ms 46936 KB Output is correct
5 Correct 8 ms 46940 KB Output is correct
6 Correct 7 ms 46940 KB Output is correct
7 Correct 9 ms 46940 KB Output is correct
8 Correct 9 ms 46940 KB Output is correct
9 Correct 7 ms 46940 KB Output is correct
10 Correct 8 ms 46940 KB Output is correct
11 Correct 8 ms 46940 KB Output is correct
12 Correct 7 ms 46940 KB Output is correct
13 Correct 8 ms 46940 KB Output is correct
14 Correct 11 ms 46936 KB Output is correct
15 Correct 8 ms 46940 KB Output is correct
16 Correct 7 ms 46940 KB Output is correct
17 Correct 7 ms 46940 KB Output is correct
18 Correct 8 ms 46936 KB Output is correct
19 Correct 8 ms 46940 KB Output is correct
20 Correct 8 ms 46940 KB Output is correct
21 Incorrect 8 ms 46936 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
22 Halted 0 ms 0 KB -

Subtask #6
0.0 / 14.0

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

Subtask #7
0.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 47192 KB Output is correct
2 Correct 8 ms 46940 KB Output is correct
3 Correct 9 ms 46940 KB Output is correct
4 Correct 8 ms 46936 KB Output is correct
5 Correct 8 ms 46940 KB Output is correct
6 Correct 7 ms 46940 KB Output is correct
7 Correct 9 ms 46940 KB Output is correct
8 Correct 9 ms 46940 KB Output is correct
9 Correct 7 ms 46940 KB Output is correct
10 Correct 8 ms 46940 KB Output is correct
11 Correct 8 ms 46940 KB Output is correct
12 Correct 7 ms 46940 KB Output is correct
13 Correct 8 ms 46940 KB Output is correct
14 Correct 11 ms 46936 KB Output is correct
15 Correct 8 ms 46940 KB Output is correct
16 Correct 7 ms 46940 KB Output is correct
17 Correct 7 ms 46940 KB Output is correct
18 Correct 8 ms 46936 KB Output is correct
19 Correct 8 ms 46940 KB Output is correct
20 Correct 8 ms 46940 KB Output is correct
21 Incorrect 8 ms 46936 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
22 Halted 0 ms 0 KB -

Subtask #8
0.0 / 17.0

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

Subtask #9
0.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 47192 KB Output is correct
2 Correct 8 ms 46940 KB Output is correct
3 Correct 9 ms 46940 KB Output is correct
4 Correct 8 ms 46936 KB Output is correct
5 Correct 8 ms 46940 KB Output is correct
6 Correct 7 ms 46940 KB Output is correct
7 Correct 9 ms 46940 KB Output is correct
8 Correct 9 ms 46940 KB Output is correct
9 Correct 7 ms 46940 KB Output is correct
10 Correct 8 ms 46940 KB Output is correct
11 Correct 8 ms 46940 KB Output is correct
12 Correct 7 ms 46940 KB Output is correct
13 Correct 8 ms 46940 KB Output is correct
14 Correct 11 ms 46936 KB Output is correct
15 Correct 8 ms 46940 KB Output is correct
16 Correct 7 ms 46940 KB Output is correct
17 Correct 7 ms 46940 KB Output is correct
18 Correct 8 ms 46936 KB Output is correct
19 Correct 8 ms 46940 KB Output is correct
20 Correct 8 ms 46940 KB Output is correct
21 Incorrect 8 ms 46936 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
22 Halted 0 ms 0 KB -