Submission #100924

#	Time	Username	Problem	Language	Result	Execution time	Memory
100924		Alexa2001	Unique Cities (JOI19_ho_t5)	C++17	4 / 100	2051 ms	275456 KiB

joi2019_ho_t5

#include <bits/stdc++.h>

using namespace std;


const int Nmax = 2e5 + 5;

int down[Nmax], ans[Nmax], level[Nmax], st[Nmax], max_ex[Nmax];
bool ap[Nmax];
vector<int> v[Nmax];
int n, M;
int tip[Nmax];


void read()
{
    int i, x, y;
    cin >> n >> M;
    for(i=1; i<n; ++i)
    {
        cin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }

    for(i=1; i<=n; ++i) cin >> tip[i];
}

void print_sol()
{
    int i;
    for(i=1; i<=n; ++i) cout << ans[i] << '\n';
}

void max_to(int &x, int y) { if(x < y) x = y; }


void dfs0(int node, int dad = 0)
{
    level[node] = level[dad] + 1;
    for(auto it : v[node])
        if(it != dad)
            dfs0(it, node);
}

pair<int,int> diametru()
{
    int i, A = 1, B = 1;

    dfs0(1);
    for(i=1; i<=n; ++i)
        if(level[i] > level[A]) A = i;

    dfs0(A);
    for(i=1; i<=n; ++i)
        if(level[i] > level[B]) B = i;

    return {A, B};
}

void dfs(int node, int dad = 0)
{
    down[node] = 1;
    level[node] = level[dad] + 1;

    for(auto it : v[node])
        if(it != dad)
        {
            dfs(it, node);
            down[node] = max(down[node], down[it] + 1);
        }

    int i, mx = 0;
    for(i=0; i<v[node].size(); ++i)
        if(v[node][i] != dad)
        {
            max_ex[v[node][i]] = mx;
            max_to(mx, down[v[node][i]]);
        }

    mx = 0;
    for(i=v[node].size()-1; i>=0; --i)
        if(v[node][i] != dad)
        {
            max_to(max_ex[v[node][i]], mx);
            max_to(mx, down[v[node][i]]);
        }
}

int cnt_dist(vector<int> &v)
{
    for(auto it : v) ap[tip[it]] = 1;

    int i, ans = 0;
    for(i=1; i<=M; ++i)
        if(ap[i])
        {
            ++ans;
            ap[i] = 0;
        }
    return ans;
}

void solve(int node, vector<int> &stramos, int dad = 0)
{
    int i;

    vector<int> see;
    for(i=0; i<stramos.size(); ++i)
        if(level[stramos[i]] <= level[node] - down[node])
            see.push_back(stramos[i]);

    max_to(ans[node], cnt_dist(see));

    //stramos.push_back(node);

    for(auto it : v[node])
        if(it != dad)
        {
            vector<int> act = stramos;
            while(act.size() && level[act.back()] >= level[node] - max_ex[it]) act.pop_back();
            act.push_back(node);

            solve(it, act, node);
        }
}

void Solve(int node)
{
    dfs(node);
    vector<int> V;
    solve(node, V);
}

int main()
{
 //   freopen("input", "r", stdin);
    cin.sync_with_stdio(false);

    read();
 //   dfs(1);
    auto P = diametru();

    Solve(P.first);
    Solve(P.second);

    print_sol();

    return 0;
}

Compilation message (stderr)

joi2019_ho_t5.cpp: In function 'void dfs(int, int)':
joi2019_ho_t5.cpp:74:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0; i<v[node].size(); ++i)
              ~^~~~~~~~~~~~~~~
joi2019_ho_t5.cpp: In function 'void solve(int, std::vector<int>&, int)':
joi2019_ho_t5.cpp:109:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0; i<stramos.size(); ++i)
              ~^~~~~~~~~~~~~~~

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