oj.uz

Submission #932765

# Submission time Handle Problem Language Result Execution time Memory
932765 2024-02-24T07:18:37 Z abcvuitunggio Beech Tree (IOI23_beechtree) C++17
5 / 100
 259 ms 204512 KB 
#include "beechtree.h"
#include <bits/stdc++.h>
using namespace std;
const int lim=200001,mxn=1e7+1;
int n,m,bad[lim],sz[lim],tin[lim],tout[lim],t,id,pos[lim],order[lim],root[lim][2],last[lim],cur,a[lim],b[lim];
int le[mxn],ri[mxn],st[mxn];
vector <int> p,c,res,ke[lim],ve[lim];
vector <pair <int, int>> ve2;
set <int> s[lim],sc[lim],tmp,C;
void dfs(int u){
    sz[u]=1;
    tin[u]=++t;
    for (int v:ke[u]){
        dfs(v);
        sz[u]+=sz[v];
    }
    tout[u]=t;
    ve[sz[u]].push_back(u);
}
int update(int node, int l, int r, int i){
    cur++;
    if (l==r){
        st[cur]++;
        return cur;
    }
    int tmp=cur,mid=(l+r)>>1;
    le[tmp]=le[node];
    ri[tmp]=ri[node];
    if (mid<i)
        ri[tmp]=update(ri[node],mid+1,r,i);
    else
        le[tmp]=update(le[node],l,mid,i);
    st[tmp]=st[le[tmp]]+st[ri[tmp]];
    return tmp;
}
int get(int node, int l, int r, int u, int v){
    if (l>v||r<u||!node)
        return 0;
    if (l>=u&&r<=v)
        return st[node];
    int mid=(l+r)>>1;
    return get(le[node],l,mid,u,v)+get(ri[node],mid+1,r,u,v);
}
int get(int i, int j, int k){
    int res=get(root[i][k],1,n,tin[j],tout[j])-1;
    return res-(k&&c[i]==c[j]);
}
void dfs2(int u){
    if (ke[u].empty()){
        s[u].insert(pos[u]);
        return;
    }
    int mx=0,bigchild=-1;
    for (int v:ke[u])
        if (sz[v]>mx){
            bigchild=v;
            mx=sz[v];
        }
    for (int v:ke[u]){
        dfs2(v);
        bad[u]|=bad[v];
    }
    if (bad[u])
        return;
    swap(s[u],s[bigchild]);
    s[u].insert(pos[u]);
    for (int v:ke[u])
        if (v!=bigchild)
            for (int i:s[v]){
                if (get(order[i],u,1)!=get(p[order[i]],u,0)){
                    bad[u]=1;
                    return;
                }
            }
    C.clear();
    for (int v:ke[u])
        if (v!=bigchild){
            for (int i:s[v]){
                s[u].insert(i);
                tmp.insert(get(order[i],u,0));
                sc[c[order[i]]].insert(get(order[i],u,1));
                C.insert(c[order[i]]);
            }
            s[v].clear();
        }
    C.insert(c[bigchild]);
    tmp.insert(sz[u]);
    auto it=tmp.begin();
    int last=-1;
    ve2.clear();
    while (it!=tmp.end()){
        int x=(*it)-last-1;
        if (x)
            ve2.push_back({x,last});
        last=*it;
        it++;
    }
    tmp.clear();
    int cnt=0;
    for (int i:C){
        int num=get(::last[i],1,n,tin[u],tout[u])-(c[u]==i);
        int id=0;
        pair <int, int> cur=ve2[0];
        sc[i].insert(num);
        auto it=sc[i].begin();
        int last=-1;
        while (it!=sc[i].end()){
            int x=(*it)-last-1;
            if (x){
                cnt+=x;
                if (!(x<=cur.first&&last==cur.second)){
                    bad[u]=1;
                    for (int i:C)
                        sc[i].clear();
                    return;
                }
                cur.first-=x;
                if (!cur.first){
                    id++;
                    cur=(id==ve2.size()?make_pair(0,0):ve2[id]);
                }
            }
            last=*it;
            it++;
        }
    }
    if (cnt<sz[bigchild])
        bad[u]=1;
    for (int i:C)
        sc[i].clear();
}
vector <int> beechtree(int N, int M, vector<int> P, vector<int> C){
    n=N,m=M,p=P,c=C;
    for (int i=1;i<n;i++)
        ke[P[i]].push_back(i);
    dfs(0);
    for (int i=n;i>=0;i--){
        sort(ve[i].begin(),ve[i].end(),[](int u, int v){return pos[p[u]]<pos[p[v]];});
        for (int j:ve[i]){
            pos[j]=++id;
            order[id]=j;
        }
    }
    for (int i=1;i<=n;i++){
        int j=order[i];
        root[j][0]=update(root[order[i-1]][0],1,n,tin[j]);
        root[j][1]=update(last[c[j]],1,n,tin[j]);
        last[c[j]]=root[j][1];
    }
    dfs2(0);
    for (int i=0;i<n;i++)
        res.push_back(bad[i]^1);
    return res;
}

Compilation message

beechtree.cpp: In function 'void dfs2(int)':
beechtree.cpp:120:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |                     cur=(id==ve2.size()?make_pair(0,0):ve2[id]);
      |                          ~~^~~~~~~~~~~~

Subtask #0
0.0 / 0.0

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

Subtask #1
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 33372 KB Output is correct
2 Correct 8 ms 33372 KB Output is correct
3 Correct 8 ms 33628 KB Output is correct
4 Correct 8 ms 33372 KB Output is correct
5 Correct 7 ms 33444 KB Output is correct
6 Correct 7 ms 33372 KB Output is correct
7 Correct 8 ms 33456 KB Output is correct
8 Correct 9 ms 33472 KB Output is correct
9 Correct 7 ms 33372 KB Output is correct
10 Correct 7 ms 33424 KB Output is correct
11 Correct 7 ms 33484 KB Output is correct
12 Correct 8 ms 33428 KB Output is correct
13 Correct 7 ms 33372 KB Output is correct
14 Correct 8 ms 33372 KB Output is correct
15 Correct 7 ms 33372 KB Output is correct
16 Correct 7 ms 33480 KB Output is correct
17 Correct 9 ms 33372 KB Output is correct
18 Correct 8 ms 33416 KB Output is correct
19 Correct 8 ms 33372 KB Output is correct
20 Correct 8 ms 33372 KB Output is correct
21 Incorrect 7 ms 33372 KB 2nd lines differ - on the 1st token, expected: '1', found: '0'
22 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 33372 KB Output is correct
2 Correct 8 ms 33372 KB Output is correct
3 Correct 8 ms 33628 KB Output is correct
4 Correct 8 ms 33372 KB Output is correct
5 Correct 7 ms 33444 KB Output is correct
6 Correct 7 ms 33372 KB Output is correct
7 Correct 213 ms 196136 KB Output is correct
8 Correct 182 ms 196120 KB Output is correct
9 Correct 7 ms 33372 KB Output is correct
10 Correct 7 ms 33428 KB Output is correct
11 Correct 7 ms 33372 KB Output is correct
12 Correct 7 ms 33372 KB Output is correct
13 Correct 10 ms 34496 KB Output is correct
14 Correct 9 ms 34464 KB Output is correct
15 Correct 9 ms 35164 KB Output is correct
16 Correct 11 ms 35164 KB Output is correct
17 Correct 259 ms 204512 KB Output is correct
18 Correct 227 ms 201420 KB Output is correct
19 Correct 197 ms 197724 KB Output is correct
20 Correct 193 ms 196048 KB Output is correct

Subtask #3
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 33372 KB Output is correct
2 Correct 7 ms 33372 KB Output is correct
3 Correct 8 ms 33372 KB Output is correct
4 Correct 7 ms 33372 KB Output is correct
5 Correct 7 ms 33408 KB Output is correct
6 Correct 7 ms 33372 KB Output is correct
7 Correct 7 ms 33372 KB Output is correct
8 Correct 7 ms 33372 KB Output is correct
9 Incorrect 7 ms 33432 KB 2nd lines differ - on the 1st token, expected: '1', found: '0'
10 Halted 0 ms 0 KB -

Subtask #4
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 33372 KB Output is correct
2 Correct 8 ms 33372 KB Output is correct
3 Correct 8 ms 33456 KB Output is correct
4 Correct 9 ms 33472 KB Output is correct
5 Correct 213 ms 196136 KB Output is correct
6 Correct 182 ms 196120 KB Output is correct
7 Incorrect 7 ms 33368 KB 2nd lines differ - on the 52nd token, expected: '1', found: '0'
8 Halted 0 ms 0 KB -

Subtask #5
0.0 / 14.0

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

Subtask #6
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 33372 KB Output is correct
2 Correct 8 ms 33372 KB Output is correct
3 Correct 8 ms 33456 KB Output is correct
4 Correct 9 ms 33472 KB Output is correct
5 Correct 7 ms 33372 KB Output is correct
6 Correct 7 ms 33424 KB Output is correct
7 Correct 7 ms 33484 KB Output is correct
8 Correct 8 ms 33428 KB Output is correct
9 Correct 7 ms 33372 KB Output is correct
10 Correct 8 ms 33372 KB Output is correct
11 Correct 7 ms 33372 KB Output is correct
12 Correct 7 ms 33480 KB Output is correct
13 Correct 9 ms 33372 KB Output is correct
14 Correct 8 ms 33416 KB Output is correct
15 Correct 8 ms 33372 KB Output is correct
16 Correct 8 ms 33372 KB Output is correct
17 Incorrect 7 ms 33372 KB 2nd lines differ - on the 1st token, expected: '1', found: '0'
18 Halted 0 ms 0 KB -

Subtask #7
0.0 / 12.0

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

Subtask #8
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 33372 KB Output is correct
2 Correct 8 ms 33372 KB Output is correct
3 Correct 8 ms 33456 KB Output is correct
4 Correct 9 ms 33472 KB Output is correct
5 Correct 7 ms 33372 KB Output is correct
6 Correct 7 ms 33424 KB Output is correct
7 Correct 7 ms 33484 KB Output is correct
8 Correct 8 ms 33428 KB Output is correct
9 Correct 7 ms 33372 KB Output is correct
10 Correct 8 ms 33372 KB Output is correct
11 Correct 7 ms 33372 KB Output is correct
12 Correct 7 ms 33480 KB Output is correct
13 Correct 9 ms 33372 KB Output is correct
14 Correct 8 ms 33416 KB Output is correct
15 Correct 8 ms 33372 KB Output is correct
16 Correct 8 ms 33372 KB Output is correct
17 Incorrect 7 ms 33372 KB 2nd lines differ - on the 1st token, expected: '1', found: '0'
18 Halted 0 ms 0 KB -

Subtask #9
0.0 / 12.0

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