oj.uz

Submission #658164

# Submission time Handle Problem Language Result Execution time Memory
658164 2022-11-12T10:21:58 Z azberjibiou Capital City (JOI20_capital_city) C++17
100 / 100
 768 ms 106472 KB 
#include <bits/stdc++.h>
using namespace std;
const int mxN=200005;
const int mxK=25;
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second
#define all(x) x.begin(), x.end()
typedef long long ll;
const ll MOD=1000000007;
const ll INF=1e18;

int N, K;
vector <int> v[mxN];
vector <int> ct[mxN];
int C[mxN];
int dep[mxN], par[mxN], sps[mxN][mxK];
int root[mxN];
int in[mxN], out[mxN], iidx;
set <pii> s;
struct cmp1{
     bool operator()(const int a, const int b)const {
        return in[a]<in[b];
     }
};
set <int, cmp1> et[mxN];
set <int> np[mxN];
int cnt[mxN];
int ans=mxN;
void dfs1(int now, int pre=-1)
{
    in[now]=++iidx;
    for(int i=1;i<=19;i++)  sps[now][i]=sps[sps[now][i-1]][i-1];
    for(int nxt : v[now])   if(nxt!=pre)
    {
        dep[nxt]=dep[now]+1;
        sps[nxt][0]=par[nxt]=now;
        dfs1(nxt, now);
    }
    out[now]=iidx;
}
int lca(int a, int b)
{
    if(dep[a]<dep[b])   swap(a, b);
    for(int i=19;i>=0;i--)
    {
        if(dep[a]-(1<<i)>=dep[b])   a=sps[a][i];
    }
    if(a==b)    return a;

    for(int i=19;i>=0;i--)
    {
        if(sps[a][i]!=sps[b][i])    a=sps[a][i], b=sps[b][i];
    }
    return sps[a][0];
}
int uf1[mxN], uf2[mxN];
void init1(){for(int i=1;i<=N;i++)  uf1[i]=i;}
void init2(){for(int i=1;i<=N;i++)  uf2[i]=i;}
int findpar1(int a){return uf1[a]==a ? a : uf1[a]=findpar1(uf1[a]);}
int findpar2(int a)
{
    a=findpar1(a);
    return uf2[a]==a ? a : uf2[a]=findpar2(uf2[a]);
}
void onion(int c1, int c2)
{
    uf1[c2]=c1;
    if(et[c1].size()<et[c2].size())
    {
        swap(np[c1], np[c2]);
        swap(et[c1], et[c2]);
    }
    for(int e : et[c2])
    {
        C[e]=c1;
        if(np[c1].find(e)!=np[c1].end())    np[c1].erase(e);
    }
    for(int e : np[c2])
    {
        if(et[c1].find(e)==et[c1].end())    np[c1].insert(e);
    }
    for(int e : et[c2]) et[c1].insert(e);
    et[c2].clear();
    np[c2].clear();
    cnt[c1]+=cnt[c2];
    root[c1]=lca(root[c1], root[c2]);
    s.insert(pii(et[c1].size(), c1));
}
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    dep[0]=-1;
    cin >> N >> K;
    for(int i=1;i<N;i++)
    {
        int a, b;
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    for(int i=1;i<=N;i++)   cin >> C[i], ct[C[i]].push_back(i);
    for(int i=1;i<=K;i++)   if(ct[i].size()==1)
    {
        cout << 0;
        return  0;
    }
    dfs1(1);
    for(int i=1;i<=K;i++)
    {
        root[i]=ct[i][0];
        for(int ele : ct[i])    root[i]=lca(root[i], ele);
    }
    for(int i=1;i<=K;i++)   s.insert(pii(ct[i].size(), i));
    for(int i=1;i<=K;i++)   for(int ele : ct[i])    et[i].insert(ele);
    for(int i=1;i<=K;i++)   for(int ele : ct[i])    if(C[par[ele]]!=i)   np[i].insert(par[ele]);
    for(int i=1;i<=K;i++)   cnt[i]=1;
    init1();
    init2();
    while(s.size())
    {
        int c1=s.begin()->se;
        s.erase(s.begin());
        if(np[c1].size()==1 && *np[c1].begin()==par[root[c1]])
        {
            ans=min(ans, cnt[c1]);
            continue;
        }
        auto it=np[c1].begin();
        int x=*it;
        if(x==par[root[c1]])    x=*(++it);
        int c2=C[x];
        if(findpar2(c2)==c1) onion(c1, c2);
        else    uf2[c1]=c2;
    }
    cout << ans-1;
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 28500 KB Output is correct
2 Correct 14 ms 28492 KB Output is correct
3 Correct 14 ms 28528 KB Output is correct
4 Correct 14 ms 28500 KB Output is correct
5 Correct 14 ms 28500 KB Output is correct
6 Correct 14 ms 28468 KB Output is correct
7 Correct 15 ms 28444 KB Output is correct
8 Correct 14 ms 28568 KB Output is correct
9 Correct 13 ms 28552 KB Output is correct
10 Correct 14 ms 28492 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 28500 KB Output is correct
2 Correct 14 ms 28492 KB Output is correct
3 Correct 14 ms 28528 KB Output is correct
4 Correct 14 ms 28500 KB Output is correct
5 Correct 14 ms 28500 KB Output is correct
6 Correct 14 ms 28468 KB Output is correct
7 Correct 15 ms 28444 KB Output is correct
8 Correct 14 ms 28568 KB Output is correct
9 Correct 13 ms 28552 KB Output is correct
10 Correct 14 ms 28492 KB Output is correct
11 Correct 16 ms 29004 KB Output is correct
12 Correct 16 ms 29044 KB Output is correct
13 Correct 17 ms 29048 KB Output is correct
14 Correct 16 ms 28992 KB Output is correct
15 Correct 16 ms 29060 KB Output is correct
16 Correct 15 ms 29044 KB Output is correct
17 Correct 15 ms 29144 KB Output is correct
18 Correct 15 ms 29056 KB Output is correct
19 Correct 16 ms 29148 KB Output is correct
20 Correct 15 ms 29044 KB Output is correct
21 Correct 16 ms 29140 KB Output is correct
22 Correct 16 ms 29268 KB Output is correct
23 Correct 16 ms 29176 KB Output is correct
24 Correct 16 ms 29140 KB Output is correct
25 Correct 16 ms 29140 KB Output is correct
26 Correct 16 ms 29204 KB Output is correct
27 Correct 18 ms 29172 KB Output is correct
28 Correct 16 ms 29176 KB Output is correct
29 Correct 16 ms 29140 KB Output is correct
30 Correct 16 ms 29140 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 365 ms 103372 KB Output is correct
2 Correct 170 ms 103984 KB Output is correct
3 Correct 368 ms 103124 KB Output is correct
4 Correct 183 ms 104008 KB Output is correct
5 Correct 367 ms 99044 KB Output is correct
6 Correct 170 ms 103756 KB Output is correct
7 Correct 348 ms 98332 KB Output is correct
8 Correct 172 ms 101064 KB Output is correct
9 Correct 593 ms 96120 KB Output is correct
10 Correct 586 ms 93408 KB Output is correct
11 Correct 636 ms 96468 KB Output is correct
12 Correct 627 ms 99180 KB Output is correct
13 Correct 615 ms 93132 KB Output is correct
14 Correct 614 ms 99404 KB Output is correct
15 Correct 623 ms 99056 KB Output is correct
16 Correct 589 ms 94048 KB Output is correct
17 Correct 620 ms 94824 KB Output is correct
18 Correct 598 ms 94756 KB Output is correct
19 Correct 613 ms 97984 KB Output is correct
20 Correct 603 ms 100316 KB Output is correct
21 Correct 15 ms 28500 KB Output is correct

Subtask #4
59.0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 28500 KB Output is correct
2 Correct 14 ms 28492 KB Output is correct
3 Correct 14 ms 28528 KB Output is correct
4 Correct 14 ms 28500 KB Output is correct
5 Correct 14 ms 28500 KB Output is correct
6 Correct 14 ms 28468 KB Output is correct
7 Correct 15 ms 28444 KB Output is correct
8 Correct 14 ms 28568 KB Output is correct
9 Correct 13 ms 28552 KB Output is correct
10 Correct 14 ms 28492 KB Output is correct
11 Correct 16 ms 29004 KB Output is correct
12 Correct 16 ms 29044 KB Output is correct
13 Correct 17 ms 29048 KB Output is correct
14 Correct 16 ms 28992 KB Output is correct
15 Correct 16 ms 29060 KB Output is correct
16 Correct 15 ms 29044 KB Output is correct
17 Correct 15 ms 29144 KB Output is correct
18 Correct 15 ms 29056 KB Output is correct
19 Correct 16 ms 29148 KB Output is correct
20 Correct 15 ms 29044 KB Output is correct
21 Correct 16 ms 29140 KB Output is correct
22 Correct 16 ms 29268 KB Output is correct
23 Correct 16 ms 29176 KB Output is correct
24 Correct 16 ms 29140 KB Output is correct
25 Correct 16 ms 29140 KB Output is correct
26 Correct 16 ms 29204 KB Output is correct
27 Correct 18 ms 29172 KB Output is correct
28 Correct 16 ms 29176 KB Output is correct
29 Correct 16 ms 29140 KB Output is correct
30 Correct 16 ms 29140 KB Output is correct
31 Correct 365 ms 103372 KB Output is correct
32 Correct 170 ms 103984 KB Output is correct
33 Correct 368 ms 103124 KB Output is correct
34 Correct 183 ms 104008 KB Output is correct
35 Correct 367 ms 99044 KB Output is correct
36 Correct 170 ms 103756 KB Output is correct
37 Correct 348 ms 98332 KB Output is correct
38 Correct 172 ms 101064 KB Output is correct
39 Correct 593 ms 96120 KB Output is correct
40 Correct 586 ms 93408 KB Output is correct
41 Correct 636 ms 96468 KB Output is correct
42 Correct 627 ms 99180 KB Output is correct
43 Correct 615 ms 93132 KB Output is correct
44 Correct 614 ms 99404 KB Output is correct
45 Correct 623 ms 99056 KB Output is correct
46 Correct 589 ms 94048 KB Output is correct
47 Correct 620 ms 94824 KB Output is correct
48 Correct 598 ms 94756 KB Output is correct
49 Correct 613 ms 97984 KB Output is correct
50 Correct 603 ms 100316 KB Output is correct
51 Correct 15 ms 28500 KB Output is correct
52 Correct 578 ms 84780 KB Output is correct
53 Correct 581 ms 84628 KB Output is correct
54 Correct 119 ms 40728 KB Output is correct
55 Correct 582 ms 84700 KB Output is correct
56 Correct 115 ms 40744 KB Output is correct
57 Correct 117 ms 40792 KB Output is correct
58 Correct 336 ms 87568 KB Output is correct
59 Correct 320 ms 88584 KB Output is correct
60 Correct 354 ms 90388 KB Output is correct
61 Correct 324 ms 89468 KB Output is correct
62 Correct 167 ms 106472 KB Output is correct
63 Correct 172 ms 106424 KB Output is correct
64 Correct 175 ms 104256 KB Output is correct
65 Correct 207 ms 106212 KB Output is correct
66 Correct 285 ms 89296 KB Output is correct
67 Correct 286 ms 89152 KB Output is correct
68 Correct 291 ms 89444 KB Output is correct
69 Correct 280 ms 89300 KB Output is correct
70 Correct 277 ms 89272 KB Output is correct
71 Correct 295 ms 89168 KB Output is correct
72 Correct 308 ms 89296 KB Output is correct
73 Correct 309 ms 88464 KB Output is correct
74 Correct 323 ms 89336 KB Output is correct
75 Correct 309 ms 89436 KB Output is correct
76 Correct 296 ms 95516 KB Output is correct
77 Correct 299 ms 90824 KB Output is correct
78 Correct 658 ms 97136 KB Output is correct
79 Correct 632 ms 95056 KB Output is correct
80 Correct 655 ms 102192 KB Output is correct
81 Correct 697 ms 98492 KB Output is correct
82 Correct 707 ms 98836 KB Output is correct
83 Correct 688 ms 95384 KB Output is correct
84 Correct 768 ms 101292 KB Output is correct
85 Correct 687 ms 99676 KB Output is correct
86 Correct 724 ms 94916 KB Output is correct
87 Correct 724 ms 96816 KB Output is correct
88 Correct 557 ms 97272 KB Output is correct
89 Correct 525 ms 93356 KB Output is correct
90 Correct 538 ms 93180 KB Output is correct
91 Correct 571 ms 95548 KB Output is correct
92 Correct 641 ms 94148 KB Output is correct
93 Correct 674 ms 93908 KB Output is correct
94 Correct 634 ms 93232 KB Output is correct
95 Correct 551 ms 94700 KB Output is correct
96 Correct 597 ms 93392 KB Output is correct
97 Correct 614 ms 95460 KB Output is correct