oj.uz

Submission #223921

# Submission time Handle Problem Language Result Execution time Memory
223921 2020-04-16T20:52:48 Z medk Capital City (JOI20_capital_city) C++14
100 / 100
 544 ms 84536 KB 
#include <bits/stdc++.h>

#define ld long double
#define ll long long
#define pb push_back
#define x first
#define y second
#define all(x) x.begin(),x.end()
#define sz(x) (int)(x.size())

using namespace std;

const int MAXN=200000;

int n,k;
int lca[20][500000];
vector<vector<int>> g(MAXN);
vector<set<int>> unvis(MAXN);
vector<int> eul,lvl(MAXN),in(MAXN),par(MAXN),color,colorLCA,dsu,dsu2,sz,highestV,doneColors(MAXN);
vector<int> vis(MAXN);

int getp(int x)
{
    if(x==dsu[x]) return x;
    return dsu[x]=getp(dsu[x]);
}

void connect(int u, int v)
{
    u=getp(u), v=getp(v);
    if(u==v) return;
    if(sz[v]>sz[u]) swap(u,v);
    dsu[v]=u;
    sz[u]+=sz[v];
    doneColors[u]+=doneColors[v];
}

int getp2(int x)
{
    if(x==dsu2[x]) return x;
    return dsu2[x]=getp2(dsu2[x]);
}
void connect2(int u, int v)
{
    u=getp2(u), v=getp2(v);
    if(u==v) return;
    if(rand()&1) swap(u,v);
    dsu2[v]=u;
    if(lvl[highestV[u]]>lvl[highestV[v]]) highestV[u]=highestV[v];
}
void makeeuler(int u, int pr, int d)
{
    par[u]=pr;
    in[u]=sz(eul);
    lvl[u]=d;
    eul.pb(u);
    for(int v:g[u])
    {
        if(v==pr) continue;
        makeeuler(v,u,d+1);
        eul.pb(u);
    }
}

int getlca(int u, int v)
{
    int l=in[u], r=in[v];
    if(l>r) swap(l,r);
    int lg=log2(r-l+1);
    return (lvl[lca[lg][l]]<=lvl[lca[lg][r-(1<<lg)+1]]?lca[lg][l]:lca[lg][r-(1<<lg)+1]);
}

int main()
{
    //freopen("test.in","r",stdin);
    ios::sync_with_stdio(0); cin.tie(0);
    cin>>n>>k;
    for(int i=0;i<k;i++) dsu.pb(i), sz.pb(1);
    for(int i=0;i<n-1;i++)
    {
        int u,v; cin>>u>>v;
        u--;v--;
        g[u].pb(v);
        g[v].pb(u);
    }
    makeeuler(0,-1,0);
    for(int i=0;i<sz(eul);i++) lca[0][i]=eul[i];
    for(int i=1;i<20;i++)
        for(int j=0;j+(1<<i)<=sz(eul);j++)
            lca[i][j] = (lvl[lca[i-1][j]]<=lvl[lca[i-1][j+(1<<(i-1))]]?lca[i-1][j]:lca[i-1][j+(1<<(i-1))]);
    for(int i=0;i<n;i++)
    {
        dsu2.pb(i), highestV.pb(i);
        int c; cin>>c; c--;
        color.pb(c);
        unvis[c].insert(i);
    }
    int ans=1e9;
    set<pair<int,int>> q;
    for(int i=0;i<k;i++)
    {
        int lc=*unvis[i].begin();
        for(int v:unvis[i])
            lc=getlca(lc,v);
        colorLCA.pb(lc);
        q.insert({-lvl[lc],lc});
    }
    for(auto p:q)
    {
        int candidLCA=p.y;
        if(candidLCA!=colorLCA[color[candidLCA]]) continue;
        queue<int> qu;
        for(int v:unvis[color[candidLCA]])
        {
            qu.push(v);
            if(v!=candidLCA) vis[v]=1;
        }
        unvis[color[candidLCA]].clear();
        doneColors[getp(color[candidLCA])]++;
        while(!qu.empty())
        {
            int v=qu.front(); qu.pop();
            while(v!=candidLCA)
            {
                if(vis[v]==2) break;
                connect(color[candidLCA],color[v]);
                if(lvl[colorLCA[color[v]]]>=lvl[candidLCA])
                {
                    int bef=sz(unvis[color[v]]);
                    unvis[color[v]].erase(v);
                    if(sz(unvis[color[v]])==0 && bef==1) doneColors[getp(color[v])]++;
                    vis[v]=2;
                    for(int t:unvis[color[v]])
                    {
                        if(vis[t]) continue;
                        vis[t]=1;
                        qu.push(t);
                        unvis[color[t]].erase(t);
                        if(sz(unvis[color[t]])==0) doneColors[getp(color[t])]++;
                    }
                }
                else break;
                connect2(v,par[v]);
                v=highestV[getp2(par[v])];
                if(vis[v]==1) break;
            }
        }
        int rep=getp(color[candidLCA]);
        if(doneColors[rep]==sz[rep]) ans=min(ans,sz[rep]-1);
    }
    cout<<ans<<'\n';
    return 0;
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 18432 KB Output is correct
2 Correct 17 ms 18432 KB Output is correct
3 Correct 16 ms 18432 KB Output is correct
4 Correct 16 ms 18432 KB Output is correct
5 Correct 17 ms 18432 KB Output is correct
6 Correct 16 ms 18432 KB Output is correct
7 Correct 16 ms 18432 KB Output is correct
8 Correct 15 ms 18432 KB Output is correct
9 Correct 17 ms 18432 KB Output is correct
10 Correct 15 ms 18304 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 18432 KB Output is correct
2 Correct 17 ms 18432 KB Output is correct
3 Correct 16 ms 18432 KB Output is correct
4 Correct 16 ms 18432 KB Output is correct
5 Correct 17 ms 18432 KB Output is correct
6 Correct 16 ms 18432 KB Output is correct
7 Correct 16 ms 18432 KB Output is correct
8 Correct 15 ms 18432 KB Output is correct
9 Correct 17 ms 18432 KB Output is correct
10 Correct 15 ms 18304 KB Output is correct
11 Correct 19 ms 18816 KB Output is correct
12 Correct 18 ms 18816 KB Output is correct
13 Correct 18 ms 18816 KB Output is correct
14 Correct 16 ms 18816 KB Output is correct
15 Correct 19 ms 18944 KB Output is correct
16 Correct 17 ms 18944 KB Output is correct
17 Correct 16 ms 18944 KB Output is correct
18 Correct 18 ms 18944 KB Output is correct
19 Correct 16 ms 18944 KB Output is correct
20 Correct 16 ms 18944 KB Output is correct
21 Correct 16 ms 18944 KB Output is correct
22 Correct 19 ms 18944 KB Output is correct
23 Correct 18 ms 18920 KB Output is correct
24 Correct 16 ms 18944 KB Output is correct
25 Correct 16 ms 18944 KB Output is correct
26 Correct 16 ms 18944 KB Output is correct
27 Correct 19 ms 18944 KB Output is correct
28 Correct 19 ms 18848 KB Output is correct
29 Correct 16 ms 18944 KB Output is correct
30 Correct 17 ms 18944 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 482 ms 83728 KB Output is correct
2 Correct 229 ms 84536 KB Output is correct
3 Correct 474 ms 83284 KB Output is correct
4 Correct 230 ms 84300 KB Output is correct
5 Correct 428 ms 79540 KB Output is correct
6 Correct 230 ms 84300 KB Output is correct
7 Correct 415 ms 80484 KB Output is correct
8 Correct 228 ms 83408 KB Output is correct
9 Correct 412 ms 78132 KB Output is correct
10 Correct 404 ms 76376 KB Output is correct
11 Correct 544 ms 78716 KB Output is correct
12 Correct 432 ms 80664 KB Output is correct
13 Correct 393 ms 75880 KB Output is correct
14 Correct 514 ms 80804 KB Output is correct
15 Correct 506 ms 80616 KB Output is correct
16 Correct 521 ms 76648 KB Output is correct
17 Correct 412 ms 77096 KB Output is correct
18 Correct 473 ms 77160 KB Output is correct
19 Correct 436 ms 79856 KB Output is correct
20 Correct 386 ms 81384 KB Output is correct
21 Correct 17 ms 18304 KB Output is correct

Subtask #4
59.0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 18432 KB Output is correct
2 Correct 17 ms 18432 KB Output is correct
3 Correct 16 ms 18432 KB Output is correct
4 Correct 16 ms 18432 KB Output is correct
5 Correct 17 ms 18432 KB Output is correct
6 Correct 16 ms 18432 KB Output is correct
7 Correct 16 ms 18432 KB Output is correct
8 Correct 15 ms 18432 KB Output is correct
9 Correct 17 ms 18432 KB Output is correct
10 Correct 15 ms 18304 KB Output is correct
11 Correct 19 ms 18816 KB Output is correct
12 Correct 18 ms 18816 KB Output is correct
13 Correct 18 ms 18816 KB Output is correct
14 Correct 16 ms 18816 KB Output is correct
15 Correct 19 ms 18944 KB Output is correct
16 Correct 17 ms 18944 KB Output is correct
17 Correct 16 ms 18944 KB Output is correct
18 Correct 18 ms 18944 KB Output is correct
19 Correct 16 ms 18944 KB Output is correct
20 Correct 16 ms 18944 KB Output is correct
21 Correct 16 ms 18944 KB Output is correct
22 Correct 19 ms 18944 KB Output is correct
23 Correct 18 ms 18920 KB Output is correct
24 Correct 16 ms 18944 KB Output is correct
25 Correct 16 ms 18944 KB Output is correct
26 Correct 16 ms 18944 KB Output is correct
27 Correct 19 ms 18944 KB Output is correct
28 Correct 19 ms 18848 KB Output is correct
29 Correct 16 ms 18944 KB Output is correct
30 Correct 17 ms 18944 KB Output is correct
31 Correct 482 ms 83728 KB Output is correct
32 Correct 229 ms 84536 KB Output is correct
33 Correct 474 ms 83284 KB Output is correct
34 Correct 230 ms 84300 KB Output is correct
35 Correct 428 ms 79540 KB Output is correct
36 Correct 230 ms 84300 KB Output is correct
37 Correct 415 ms 80484 KB Output is correct
38 Correct 228 ms 83408 KB Output is correct
39 Correct 412 ms 78132 KB Output is correct
40 Correct 404 ms 76376 KB Output is correct
41 Correct 544 ms 78716 KB Output is correct
42 Correct 432 ms 80664 KB Output is correct
43 Correct 393 ms 75880 KB Output is correct
44 Correct 514 ms 80804 KB Output is correct
45 Correct 506 ms 80616 KB Output is correct
46 Correct 521 ms 76648 KB Output is correct
47 Correct 412 ms 77096 KB Output is correct
48 Correct 473 ms 77160 KB Output is correct
49 Correct 436 ms 79856 KB Output is correct
50 Correct 386 ms 81384 KB Output is correct
51 Correct 17 ms 18304 KB Output is correct
52 Correct 358 ms 67052 KB Output is correct
53 Correct 407 ms 67144 KB Output is correct
54 Correct 364 ms 66920 KB Output is correct
55 Correct 368 ms 66924 KB Output is correct
56 Correct 362 ms 66920 KB Output is correct
57 Correct 358 ms 66924 KB Output is correct
58 Correct 317 ms 71652 KB Output is correct
59 Correct 332 ms 72424 KB Output is correct
60 Correct 331 ms 70372 KB Output is correct
61 Correct 404 ms 70188 KB Output is correct
62 Correct 222 ms 84368 KB Output is correct
63 Correct 223 ms 84324 KB Output is correct
64 Correct 213 ms 83556 KB Output is correct
65 Correct 217 ms 84320 KB Output is correct
66 Correct 305 ms 73656 KB Output is correct
67 Correct 338 ms 73576 KB Output is correct
68 Correct 267 ms 73576 KB Output is correct
69 Correct 259 ms 73576 KB Output is correct
70 Correct 266 ms 73692 KB Output is correct
71 Correct 312 ms 73804 KB Output is correct
72 Correct 247 ms 73704 KB Output is correct
73 Correct 402 ms 72908 KB Output is correct
74 Correct 248 ms 73576 KB Output is correct
75 Correct 279 ms 73576 KB Output is correct
76 Correct 457 ms 76492 KB Output is correct
77 Correct 380 ms 74980 KB Output is correct
78 Correct 409 ms 77032 KB Output is correct
79 Correct 511 ms 75368 KB Output is correct
80 Correct 398 ms 81256 KB Output is correct
81 Correct 421 ms 78312 KB Output is correct
82 Correct 404 ms 78440 KB Output is correct
83 Correct 426 ms 75700 KB Output is correct
84 Correct 483 ms 80488 KB Output is correct
85 Correct 485 ms 79156 KB Output is correct
86 Correct 484 ms 75496 KB Output is correct
87 Correct 506 ms 76776 KB Output is correct
88 Correct 373 ms 77652 KB Output is correct
89 Correct 353 ms 74344 KB Output is correct
90 Correct 443 ms 74364 KB Output is correct
91 Correct 348 ms 76136 KB Output is correct
92 Correct 357 ms 74856 KB Output is correct
93 Correct 346 ms 74852 KB Output is correct
94 Correct 431 ms 74352 KB Output is correct
95 Correct 462 ms 75368 KB Output is correct
96 Correct 461 ms 74344 KB Output is correct
97 Correct 349 ms 75880 KB Output is correct