oj.uz

Submission #1078558

# Submission time Handle Problem Language Result Execution time Memory
1078558 2024-08-27T20:56:54 Z vjudge1 Unique Cities (JOI19_ho_t5) C++17
32 / 100
 221 ms 41068 KB 
    #include<bits/stdc++.h>
    #define ll long long
    #define pii pair<int,int>
    #define pll pair<ll,ll>
    #define plx pair<ll,int>
    #define f first
    #define s second
    #define pb push_back
    #define all(x) x.begin(),x.end()
    #define vi vector<int>
    #define vl vector<ll>
    #define vvi vector<vi>
    using namespace std;
    const int mxn=2e5+5,inf=998244353;
    vector<int>g[mxn];
    int c[mxn];
    int ans[mxn]{0};
    stack<int>st;
    int cc[mxn]{0},cur=0;
    int d[mxn]{0},D[mxn]{0};
    void add(int x){
        if(++cc[c[D[x]]]==1)cur++;
        st.push(x);
    }
    void del(int x){
        while(!st.empty()&&st.top()>=x){
            if(--cc[c[D[st.top()]]]==0)cur--;
            st.pop();
        }
    }
    pii mx[mxn][2];
    int tmp=0,mem=0;
    void precal(int u,int p){
        if(mem<d[u])mem=d[u],tmp=u;
        mx[u][0]=mx[u][1]={0,0};
        for(auto v:g[u]){
            if(v==p)continue;
            d[v]=d[u]+1;precal(v,u);
            pii mxe = {mx[v][0].f+1,v};
            if(mxe>mx[u][0])swap(mxe,mx[u][0]);
            if(mxe>mx[u][1])swap(mxe,mx[u][1]);
        }
    }
    void cal(int u,int p,int de){
        D[de]=u;
        if(mx[u][0].s){
            if(mx[u][1].s)del(de-mx[u][1].f);
            add(de);
            cal(mx[u][0].s,u,de+1);
            del(de-mx[u][0].f);
        }if(!st.empty()&&st.top()==de)del(de);
        ans[u]=max(ans[u],cur);
        for(auto v:g[u]){
            if(v==p||v==mx[u][0].s)continue;
            if(st.empty()||st.top()!=de)add(de);
            cal(v,u,de+1);
        }
    }
    int main(){
        ios_base::sync_with_stdio(0);cin.tie(0);
        int n,m;cin>>n>>m;
        for(int i=1;i<=n-1;i++){
            int u,v;cin>>u>>v;g[u].pb(v);g[v].pb(u);
        }for(int i=1;i<=n;i++)cin>>c[i];
        precal(1,1);int rt1=tmp;memset(d,0,sizeof d);mem=0;tmp=0;
        precal(rt1,rt1);int rt2=tmp;
        cal(rt1,rt1,0);memset(cc,0,sizeof cc);memset(D,0,sizeof D);
        while(!st.empty())st.pop();memset(d,0,sizeof d);
        precal(rt2,rt2);cal(rt2,rt2,0);
        for(int i=1;i<=n;i++)cout<<ans[i]<<'\n';
    }

Compilation message

joi2019_ho_t5.cpp: In function 'int main()':
joi2019_ho_t5.cpp:68:9: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   68 |         while(!st.empty())st.pop();memset(d,0,sizeof d);
      |         ^~~~~
joi2019_ho_t5.cpp:68:36: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   68 |         while(!st.empty())st.pop();memset(d,0,sizeof d);
      |                                    ^~~~~~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7512 KB Output is correct
2 Incorrect 4 ms 7484 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 15516 KB Output is correct
2 Correct 76 ms 26708 KB Output is correct
3 Correct 18 ms 10840 KB Output is correct
4 Correct 148 ms 21840 KB Output is correct
5 Correct 173 ms 41068 KB Output is correct
6 Correct 161 ms 31312 KB Output is correct
7 Correct 136 ms 21964 KB Output is correct
8 Correct 123 ms 23632 KB Output is correct
9 Correct 174 ms 23124 KB Output is correct
10 Correct 145 ms 23076 KB Output is correct
11 Correct 77 ms 22380 KB Output is correct
12 Correct 172 ms 33652 KB Output is correct
13 Correct 221 ms 31064 KB Output is correct
14 Correct 174 ms 30580 KB Output is correct
15 Correct 106 ms 22212 KB Output is correct
16 Correct 173 ms 35064 KB Output is correct
17 Correct 168 ms 31452 KB Output is correct

Subtask #3
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 112 ms 19792 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7512 KB Output is correct
2 Incorrect 4 ms 7484 KB Output isn't correct
3 Halted 0 ms 0 KB -