Submission #254188

#	Time	Username	Problem	Language	Result	Execution time	Memory
254188		Atill83	Unique Cities (JOI19_ho_t5)	C++14	100 / 100	447 ms	43884 KiB

joi2019_ho_t5

#include <bits/stdc++.h>
#define ff first
#define ss second
#define endl '\n'
using namespace std;
const long long INF = (long long) 1e18;
const int mod = (int) 1e9+7;
const int MAXN = (int) 3e5+5;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
ll n, m;

vector<int> adj[MAXN];
int c[MAXN];
int mxd[MAXN][2];
int ans[MAXN];
struct diam{
    int a, b;
    int mx;


    void dfs(int v, int par, int len){
        if(len > mx){
            mx = len;
            a = v;
        }
        for(int j: adj[v]){
            if(j == par) continue;
            dfs(j, v, len + 1);
        }
    }


    void fnd(){
        mx = 0;
        dfs(1, -1, 0);
        mx = 0;
        b = a;
        dfs(b, -1, 0);
    }

} dia;

int der[MAXN];

struct st{
    vector<int> g, s;
    int sz = 0;
    int cntd = 0;
    void ini(){
        g.resize(m + 1, 0);
    }
    void add(int v){
        s.push_back(v);
        sz++;
        cntd += (g[c[v]] == 0);
        g[c[v]]++;
    }

    void del(int cur){
        while(sz && cur <= der[s.back()]){
            g[c[s.back()]]--;
            cntd -= (g[c[s.back()]] == 0);
            s.pop_back();
            sz--;
        }
    }
} stt;

void upd(int a, int val){
    if(mxd[a][1] < val) mxd[a][1] = val;
    if(mxd[a][1] > mxd[a][0]) swap(mxd[a][0], mxd[a][1]);
}

int deep[MAXN];
void dfs1(int v, int par){
    der[v] = der[par] + 1;
    mxd[v][0] = mxd[v][1] = der[v];
    deep[v] = v;
    for(int j: adj[v]){
        if(j == par) continue;
        dfs1(j, v);
        upd(v, mxd[j][0]);
        if(mxd[j][0] == mxd[v][0]){
            deep[v] = j;
        }
    }
}

void dfs(int v, int par){
    stt.del(2*der[v] - mxd[v][1]);
    stt.add(v);

    for(int j: adj[v]){
        if(j != deep[v]) continue;
        dfs(j, v);
    }
    stt.del(2*der[v] - mxd[v][0]);
    ans[v] = max(ans[v], stt.cntd);

    for(int j: adj[v]){
        if(j == deep[v] || j == par) continue;
        if(stt.sz == 0 || stt.s.back() != v) stt.add(v);
        dfs(j, v);
    }
    stt.del(der[v]);
}





int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);

    #ifdef Local
        freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/int.txt","r",stdin);
        freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/out.txt","w",stdout);
    #endif

    cin>>n>>m;

    stt.ini();

    for(int i = 0; i < n - 1; i++){
        int a, b;
        cin>>a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    for(int i = 1; i <= n; i++)
        cin>>c[i];

    dia.fnd();

    dfs1(dia.a, 0);
    dfs(dia.a, 0);

    dfs1(dia.b, 0);
    dfs(dia.b, 0);

    for(int i = 1; i <= n; i++) cout<<ans[i]<<endl;
    

    #ifdef Local
        cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
    #endif
}

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