Submission #267096

#	Time	Username	Problem	Language	Result	Execution time	Memory
267096		MKopchev	Unique Cities (JOI19_ho_t5)	C++14	100 / 100	724 ms	53368 KiB

joi2019_ho_t5

#include<bits/stdc++.h>
using namespace std;
const int nmax=2e5+42;

int n,m;

vector<int> adj[nmax];
int colour[nmax];

int dist[nmax];

void dfs_dist(int node,int par,int d)
{
    dist[node]=d;

    for(auto k:adj[node])
        if(k!=par)dfs_dist(k,node,d+1);
}
int farthest(int node)
{
    dfs_dist(node,node,0);

    int ret=1;
    for(int i=1;i<=n;i++)
        if(dist[ret]<dist[i])ret=i;

    return ret;
}

int depth[nmax],height[nmax];

void dfs_depth(int node,int par)
{
    height[node]=height[par]+1;

    for(auto k:adj[node])
        if(k!=par)
        {
            dfs_depth(k,node);
            depth[node]=max(depth[node],depth[k]);
        }
    depth[node]++;
}

int seen[nmax],diff=0;

int outp[nmax];

stack<int> active;

void my_push(int node)
{
    if(seen[colour[node]]==0)diff++;
    seen[colour[node]]++;
    active.push(node);
}
void my_pop()
{
    if(seen[colour[active.top()]]==1)diff--;
    seen[colour[active.top()]]--;
    active.pop();
}
bool cmp(pair<int/*depth*/,int/*node*/> a,pair<int/*depth*/,int/*node*/> b)
{
    return a.first>b.first;
}

void print(stack<int> s)
{
    while(s.size())
    {
        cout<<s.top()<<" ";
        s.pop();
    }
    cout<<endl;
}
void dfs_solve(int node,int par)
{
    if(par!=node)
    {
        my_push(par);
    }

    vector< pair<int/*depth*/,int/*node*/> > to={};

    for(auto k:adj[node])
        if(k!=par)to.push_back({depth[k],k});

    sort(to.begin(),to.end(),cmp);
    /*
    cout<<node<<" -> "<<active.size()<<" "<<diff<<endl;
    for(int i=1;i<=n;i++)cout<<seen[i]<<" ";cout<<endl;

    print(active);

    cout<<"---"<<endl;
    */

    for(auto k:to)
    {
        int mx_depth=0;

        if(k==to[0])
        {
            if(to.size()>1)mx_depth=to[1].first;
        }
        else mx_depth=to[0].first;

        //cout<<node<<" "<<par<<" "<<k.first<<" "<<k.second<<" "<<active.size()<<endl;

        while(active.size()>=1&&height[k.second]-height[active.top()]<=mx_depth+1)my_pop();

        //cout<<"became "<<active.size()<<endl;

        dfs_solve(k.second,node);
    }

    if(active.size()&&active.top()==node)my_pop();

    while(active.size()&&height[node]-height[active.top()]<depth[node])my_pop();
    /*
    cout<<"ENDING "<<endl;
    cout<<node<<" -> "<<active.size()<<" "<<diff<<endl;
    for(int i=1;i<=n;i++)cout<<seen[i]<<" ";cout<<endl;

    print(active);

    cout<<"---"<<endl;
    */

    outp[node]=max(outp[node],diff);
}
void solve(int node)
{
    memset(depth,0,sizeof(depth));
    memset(height,0,sizeof(height));

    //cout<<"\tsolve "<<node<<endl;

    dfs_depth(node,node);

    dfs_solve(node,node);
}
int main()
{
    scanf("%i%i",&n,&m);

    for(int i=1;i<n;i++)
    {
        int u,v;
        scanf("%i%i",&u,&v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    for(int i=1;i<=n;i++)scanf("%i",&colour[i]);

    int u=farthest(1);
    int v=farthest(u);

    solve(u);
    solve(v);

    for(int i=1;i<=n;i++)printf("%i\n",outp[i]);
    return 0;
}

Compilation message (stderr)

joi2019_ho_t5.cpp: In function 'int main()':
joi2019_ho_t5.cpp:146:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  146 |     scanf("%i%i",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~
joi2019_ho_t5.cpp:151:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  151 |         scanf("%i%i",&u,&v);
      |         ~~~~~^~~~~~~~~~~~~~
joi2019_ho_t5.cpp:156:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  156 |     for(int i=1;i<=n;i++)scanf("%i",&colour[i]);
      |                          ~~~~~^~~~~~~~~~~~~~~~~

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