Submission #1181232

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181232		pythontest	Unique Cities (JOI19_ho_t5)	C++20	100 / 100	602 ms	38876 KiB

joi2019_ho_t5

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
constexpr int N=2e5+10,MJ=20;
int n,m,s1,s2;
vector<int> graf[N];
int dist[N],drzewo[1<<MJ],ile[N],vals[N],w1[N],w2[N],glebpod[N],d[N],puste=0;
bool ispuste[N];
vector<int> stosdfs;
void bfs(int from){
    queue<int> kol;
    for(int i=0;i<=n;i++) dist[i]=1e9;
    dist[from]=0;
    kol.push(from);
    while(!kol.empty()){
        auto top = kol.front();
        kol.pop();
        for(auto x:graf[top]){
            if(dist[x]>dist[top]+1){
                dist[x]=dist[top]+1;
                kol.push(x);
            }
        }
    }
}
int maxdist(){
    int w=1;
    for(int i=1;i<=n;i++){
        if(dist[w]<dist[i]){
            w=i;
        }
    }
    return w;
}
void initdrzewko(){
    for(int i=0;i<(1<<MJ);i++) drzewo[i]=0;
}
int read(int w){
    w+=1<<(MJ-1);
    int wyn=0;
    while(w>0){
        wyn+=drzewo[w];
        w>>=1;
    }
    return wyn;
}
void update(int a, int b, int s){
    a--;b++;
    a+=1<<(MJ-1);b+=1<<(MJ-1);
    while((a>>1)!=(b>>1)){
        if(a%2==0) drzewo[a+1]+=s;
        if(b%2==1) drzewo[b-1]+=s;
        a>>=1;
        b>>=1;
    }
}
void predfs(int act, int from){
    glebpod[act]=1;
    for(auto x:graf[act]){
        if(x==from) continue;
        d[x]=d[act]+1;
        predfs(x,act);
        glebpod[act]=max(glebpod[act],glebpod[x]+1);
    }
}
void solvedfs(int act, int from, int *wynik){
    stosdfs.push_back(act);
    if(d[act]>1){
        for(auto x:graf[act]){
            if(x==from) continue;
            int dol = d[act]-1;
            int gora = max(1,d[act]-glebpod[x]);
            update(gora,dol,1);
        }
    }
    if(d[act]>2){
        int dol = d[act]-2;
        int gora = max(1,d[act]-glebpod[act]-1);
        update(gora,dol,-1);
        for(int _=0;_<2;_++){
            if(read(gora)==0){
                ile[vals[stosdfs[gora]]]++;
                int ilev = ile[vals[stosdfs[gora]]];
                if(ilev==1)
                    puste++;
            }
            gora++;
        }
    }
    wynik[act]=puste;
    if(d[act]==2&&graf[act].size()==1)
        wynik[act]++;
    for(auto x:graf[act]){
        if(x==from) continue;
        solvedfs(x,act,wynik);
    }
    if(d[act]>2){
        int dol = d[act]-2;
        int gora = max(1,d[act]-glebpod[act]-1);
        update(gora,dol,1);
        for(int _=0;_<2;_++){
            if((read(gora)==1&&gora<=dol)||(gora>dol && read(gora)==0)){
                ile[vals[stosdfs[gora]]]--;
                int ilev = ile[vals[stosdfs[gora]]];
                if(ilev==0) puste--;
            }
            gora++;
        }
    }
    if(d[act]>1){
        for(auto x:graf[act]){
            if(x==from) continue;
            int dol = d[act]-1;
            int gora = max(1,d[act]-glebpod[x]);
            update(gora,dol,-1);
        }
    }
    stosdfs.pop_back();
}
void runalgo(int from, int *wynik){
    initdrzewko();
    for(int i=0;i<m;i++) ile[i]=0;
    stosdfs.push_back(-1);
    d[from]=1;
    predfs(from,0);
    solvedfs(from,0,wynik);
    stosdfs.pop_back();
}
int main() {
    scanf("%d %d",&n,&m);
    for(int i=1;i<n;i++){
        int a,b;
        scanf("%d %d",&a,&b);
        graf[a].push_back(b);
        graf[b].push_back(a);
    }
    for(int i=1;i<=n;i++) scanf("%d",&vals[i]);
    bfs(1);s1=maxdist();
    bfs(s1);s2=maxdist();
    runalgo(s1,w1);
    runalgo(s2,w2);
    for(int i=1;i<=n;i++) printf("%d\n",max(w1[i],w2[i]));
    return 0;
}

Compilation message (stderr)

joi2019_ho_t5.cpp: In function 'int main()':
joi2019_ho_t5.cpp:132:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  132 |     scanf("%d %d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~
joi2019_ho_t5.cpp:135:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  135 |         scanf("%d %d",&a,&b);
      |         ~~~~~^~~~~~~~~~~~~~~
joi2019_ho_t5.cpp:139:32: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  139 |     for(int i=1;i<=n;i++) scanf("%d",&vals[i]);
      |                           ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 32 / 32
• Subtask 3: 32 / 32
• Subtask 4: 32 / 32