oj.uz

Submission #694078

# Submission time Handle Problem Language Result Execution time Memory
694078 2023-02-03T17:31:28 Z tamthegod Mergers (JOI19_mergers) C++17
70 / 100
 1865 ms 262144 KB 
// Make the best become better
// No room for laziness
#include<bits/stdc++.h>

#define int long long
#define pb push_back
#define fi first
#define se second
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxN = 1e6 + 5;
const int mod = 1e9 + 7;
const ll oo = 1e18;
int n, m;
vector<int> adj[maxN];
vector<int> vc[maxN];
int f[maxN][20];
int depth[maxN];
pair<int, int> e[maxN];
int sum[maxN];
int lab[maxN];
int deg[maxN];
void ReadInput()
{
    cin >> n >> m;
    for(int i=1; i<n; i++)
    {
        int u, v;
        cin >> u >> v;
        e[i] = {u, v};
        adj[u].pb(v);
        adj[v].pb(u);
    }
    for(int i=1; i<=n; i++)
    {
        int x;
        cin >> x;
        vc[x].pb(i);
    }
}
int Findset(int u)
{
    return lab[u] < 0 ? u : lab[u] = Findset(lab[u]);
}
void Unite(int u, int v)
{
    int r = Findset(u), s = Findset(v);
    if(r == s) return;
    if(lab[r] > lab[s]) swap(r, s);
    lab[r] += lab[s];
    lab[s] = r;
}
void dfs(int u, int par)
{
    for(int v : adj[u])
    {
        if(v == par) continue;
        f[v][0] = u;
        depth[v] = depth[u] + 1;
        for(int i=1; i<=18; i++)
            f[v][i] = f[f[v][i - 1]][i - 1];
        dfs(v, u);
    }
}
int lca(int u, int v)
{
    if(depth[u] < depth[v]) swap(u, v);
    int k = depth[u] - depth[v];
    for(int i=19; i>=0; i--)
        if((k >> i) & 1)
            u = f[u][i];
    if(u == v) return u;
    for(int i=19; i>=0; i--)
        if(f[u][i] != f[v][i])
        {
            u = f[u][i];
            v = f[v][i];
        }
    return f[u][0];
}
void dfs1(int u, int par)
{
    for(int v : adj[u])
    {
        if(v == par) continue;
        dfs1(v, u);
        sum[u] += sum[v];
    }
    if(sum[u]) Unite(u, par);
}
void Solve()
{
    dfs(1, 0);
    for(int i=1; i<=m; i++)
    {
        if(vc[i].empty()) continue;
        int tmp = vc[i][0];
        for(int v : vc[i])
        {
            sum[v] += -1;
            tmp = lca(tmp, v);
        }
        sum[tmp] += vc[i].size();
       // cout << tmp << " ";
    }
    memset(lab, -1, sizeof lab);
    dfs1(1, 0);
    map<pair<int, int>, int> mp;
    for(int i=1; i<n; i++)
    {
        int u = Findset(e[i].fi), v = Findset(e[i].se);
        if(u == v || mp[{u, v}]) continue;
        deg[u]++;
        deg[v]++;
        mp[{u, v}] = mp[{v, u}] = 1;
    }
    int cnt = 0;
    for(int i=1; i<=n; i++)
    {
      //  cout << Findset(i) << " ";
        if(lab[i] > 0) continue;
        if(deg[i] == 1) cnt++;
    }
    cout << (cnt + 1) / 2;
}
int32_t main()
{
    //freopen("sol.inp", "r", stdin);
    //freopen("sol.out", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    ReadInput();
    Solve();
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 55024 KB Output is correct
2 Correct 28 ms 55100 KB Output is correct
3 Correct 27 ms 55140 KB Output is correct
4 Correct 26 ms 55132 KB Output is correct
5 Correct 26 ms 55048 KB Output is correct
6 Correct 26 ms 55096 KB Output is correct
7 Correct 26 ms 55144 KB Output is correct
8 Correct 26 ms 55188 KB Output is correct
9 Correct 25 ms 55100 KB Output is correct
10 Correct 29 ms 55104 KB Output is correct
11 Correct 33 ms 55100 KB Output is correct
12 Correct 26 ms 55136 KB Output is correct
13 Correct 26 ms 55164 KB Output is correct
14 Correct 24 ms 55108 KB Output is correct
15 Correct 25 ms 55156 KB Output is correct
16 Correct 25 ms 55116 KB Output is correct
17 Correct 26 ms 55100 KB Output is correct
18 Correct 26 ms 55176 KB Output is correct
19 Correct 26 ms 55140 KB Output is correct
20 Correct 26 ms 55072 KB Output is correct
21 Correct 26 ms 55124 KB Output is correct
22 Correct 26 ms 55124 KB Output is correct
23 Correct 26 ms 55096 KB Output is correct
24 Correct 28 ms 55088 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 55024 KB Output is correct
2 Correct 28 ms 55100 KB Output is correct
3 Correct 27 ms 55140 KB Output is correct
4 Correct 26 ms 55132 KB Output is correct
5 Correct 26 ms 55048 KB Output is correct
6 Correct 26 ms 55096 KB Output is correct
7 Correct 26 ms 55144 KB Output is correct
8 Correct 26 ms 55188 KB Output is correct
9 Correct 25 ms 55100 KB Output is correct
10 Correct 29 ms 55104 KB Output is correct
11 Correct 33 ms 55100 KB Output is correct
12 Correct 26 ms 55136 KB Output is correct
13 Correct 26 ms 55164 KB Output is correct
14 Correct 24 ms 55108 KB Output is correct
15 Correct 25 ms 55156 KB Output is correct
16 Correct 25 ms 55116 KB Output is correct
17 Correct 26 ms 55100 KB Output is correct
18 Correct 26 ms 55176 KB Output is correct
19 Correct 26 ms 55140 KB Output is correct
20 Correct 26 ms 55072 KB Output is correct
21 Correct 26 ms 55124 KB Output is correct
22 Correct 26 ms 55124 KB Output is correct
23 Correct 26 ms 55096 KB Output is correct
24 Correct 28 ms 55088 KB Output is correct
25 Correct 25 ms 55064 KB Output is correct
26 Correct 30 ms 56376 KB Output is correct
27 Correct 31 ms 55940 KB Output is correct
28 Correct 29 ms 56324 KB Output is correct
29 Correct 34 ms 56356 KB Output is correct
30 Correct 27 ms 55848 KB Output is correct
31 Correct 25 ms 55124 KB Output is correct
32 Correct 29 ms 56156 KB Output is correct
33 Correct 28 ms 55100 KB Output is correct
34 Correct 32 ms 55864 KB Output is correct
35 Correct 31 ms 56252 KB Output is correct
36 Correct 28 ms 55892 KB Output is correct
37 Correct 28 ms 55932 KB Output is correct
38 Correct 28 ms 55072 KB Output is correct
39 Correct 33 ms 55972 KB Output is correct
40 Correct 28 ms 55928 KB Output is correct
41 Correct 30 ms 55928 KB Output is correct
42 Correct 28 ms 56020 KB Output is correct
43 Correct 27 ms 56020 KB Output is correct
44 Correct 26 ms 55124 KB Output is correct
45 Correct 30 ms 55936 KB Output is correct
46 Correct 27 ms 55964 KB Output is correct
47 Correct 25 ms 55116 KB Output is correct
48 Correct 34 ms 56012 KB Output is correct
49 Correct 29 ms 56276 KB Output is correct
50 Correct 30 ms 56328 KB Output is correct
51 Correct 34 ms 55868 KB Output is correct
52 Correct 33 ms 55888 KB Output is correct
53 Correct 28 ms 55932 KB Output is correct
54 Correct 29 ms 55896 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 55024 KB Output is correct
2 Correct 28 ms 55100 KB Output is correct
3 Correct 27 ms 55140 KB Output is correct
4 Correct 26 ms 55132 KB Output is correct
5 Correct 26 ms 55048 KB Output is correct
6 Correct 26 ms 55096 KB Output is correct
7 Correct 26 ms 55144 KB Output is correct
8 Correct 26 ms 55188 KB Output is correct
9 Correct 25 ms 55100 KB Output is correct
10 Correct 29 ms 55104 KB Output is correct
11 Correct 33 ms 55100 KB Output is correct
12 Correct 26 ms 55136 KB Output is correct
13 Correct 26 ms 55164 KB Output is correct
14 Correct 24 ms 55108 KB Output is correct
15 Correct 25 ms 55156 KB Output is correct
16 Correct 25 ms 55116 KB Output is correct
17 Correct 26 ms 55100 KB Output is correct
18 Correct 26 ms 55176 KB Output is correct
19 Correct 26 ms 55140 KB Output is correct
20 Correct 26 ms 55072 KB Output is correct
21 Correct 26 ms 55124 KB Output is correct
22 Correct 26 ms 55124 KB Output is correct
23 Correct 26 ms 55096 KB Output is correct
24 Correct 28 ms 55088 KB Output is correct
25 Correct 25 ms 55168 KB Output is correct
26 Correct 95 ms 80296 KB Output is correct
27 Correct 124 ms 80156 KB Output is correct
28 Correct 28 ms 55908 KB Output is correct
29 Correct 27 ms 55152 KB Output is correct
30 Correct 26 ms 55124 KB Output is correct
31 Correct 131 ms 80196 KB Output is correct
32 Correct 27 ms 55872 KB Output is correct
33 Correct 173 ms 85248 KB Output is correct
34 Correct 130 ms 80148 KB Output is correct
35 Correct 27 ms 55916 KB Output is correct
36 Correct 145 ms 80336 KB Output is correct
37 Correct 30 ms 55936 KB Output is correct
38 Correct 30 ms 55892 KB Output is correct
39 Correct 100 ms 80260 KB Output is correct
40 Correct 29 ms 56012 KB Output is correct
41 Correct 114 ms 79836 KB Output is correct
42 Correct 181 ms 81552 KB Output is correct
43 Correct 30 ms 55116 KB Output is correct
44 Correct 143 ms 85340 KB Output is correct
45 Correct 142 ms 83780 KB Output is correct
46 Correct 28 ms 55892 KB Output is correct
47 Correct 29 ms 55892 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 78996 KB Output is correct
2 Correct 196 ms 94292 KB Output is correct
3 Correct 30 ms 56144 KB Output is correct
4 Correct 33 ms 55864 KB Output is correct
5 Correct 26 ms 55124 KB Output is correct
6 Correct 29 ms 55072 KB Output is correct
7 Correct 30 ms 55788 KB Output is correct
8 Correct 147 ms 83300 KB Output is correct
9 Correct 28 ms 55852 KB Output is correct
10 Correct 123 ms 81036 KB Output is correct
11 Correct 27 ms 55156 KB Output is correct
12 Correct 136 ms 80588 KB Output is correct
13 Correct 164 ms 84548 KB Output is correct
14 Correct 251 ms 95820 KB Output is correct
15 Correct 94 ms 80272 KB Output is correct
16 Correct 29 ms 55968 KB Output is correct
17 Correct 26 ms 55096 KB Output is correct
18 Correct 185 ms 93296 KB Output is correct
19 Correct 251 ms 98356 KB Output is correct
20 Correct 29 ms 55884 KB Output is correct
21 Correct 26 ms 55124 KB Output is correct
22 Correct 124 ms 84368 KB Output is correct
23 Correct 28 ms 55976 KB Output is correct
24 Correct 142 ms 82488 KB Output is correct
25 Correct 266 ms 98124 KB Output is correct
26 Correct 29 ms 56276 KB Output is correct
27 Correct 30 ms 56396 KB Output is correct
28 Correct 32 ms 55892 KB Output is correct
29 Correct 28 ms 55888 KB Output is correct
30 Correct 27 ms 55992 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 55024 KB Output is correct
2 Correct 28 ms 55100 KB Output is correct
3 Correct 27 ms 55140 KB Output is correct
4 Correct 26 ms 55132 KB Output is correct
5 Correct 26 ms 55048 KB Output is correct
6 Correct 26 ms 55096 KB Output is correct
7 Correct 26 ms 55144 KB Output is correct
8 Correct 26 ms 55188 KB Output is correct
9 Correct 25 ms 55100 KB Output is correct
10 Correct 29 ms 55104 KB Output is correct
11 Correct 33 ms 55100 KB Output is correct
12 Correct 26 ms 55136 KB Output is correct
13 Correct 26 ms 55164 KB Output is correct
14 Correct 24 ms 55108 KB Output is correct
15 Correct 25 ms 55156 KB Output is correct
16 Correct 25 ms 55116 KB Output is correct
17 Correct 26 ms 55100 KB Output is correct
18 Correct 26 ms 55176 KB Output is correct
19 Correct 26 ms 55140 KB Output is correct
20 Correct 26 ms 55072 KB Output is correct
21 Correct 26 ms 55124 KB Output is correct
22 Correct 26 ms 55124 KB Output is correct
23 Correct 26 ms 55096 KB Output is correct
24 Correct 28 ms 55088 KB Output is correct
25 Correct 25 ms 55064 KB Output is correct
26 Correct 30 ms 56376 KB Output is correct
27 Correct 31 ms 55940 KB Output is correct
28 Correct 29 ms 56324 KB Output is correct
29 Correct 34 ms 56356 KB Output is correct
30 Correct 27 ms 55848 KB Output is correct
31 Correct 25 ms 55124 KB Output is correct
32 Correct 29 ms 56156 KB Output is correct
33 Correct 28 ms 55100 KB Output is correct
34 Correct 32 ms 55864 KB Output is correct
35 Correct 31 ms 56252 KB Output is correct
36 Correct 28 ms 55892 KB Output is correct
37 Correct 28 ms 55932 KB Output is correct
38 Correct 28 ms 55072 KB Output is correct
39 Correct 33 ms 55972 KB Output is correct
40 Correct 28 ms 55928 KB Output is correct
41 Correct 30 ms 55928 KB Output is correct
42 Correct 28 ms 56020 KB Output is correct
43 Correct 27 ms 56020 KB Output is correct
44 Correct 26 ms 55124 KB Output is correct
45 Correct 30 ms 55936 KB Output is correct
46 Correct 27 ms 55964 KB Output is correct
47 Correct 25 ms 55116 KB Output is correct
48 Correct 34 ms 56012 KB Output is correct
49 Correct 29 ms 56276 KB Output is correct
50 Correct 30 ms 56328 KB Output is correct
51 Correct 34 ms 55868 KB Output is correct
52 Correct 33 ms 55888 KB Output is correct
53 Correct 28 ms 55932 KB Output is correct
54 Correct 29 ms 55896 KB Output is correct
55 Correct 25 ms 55168 KB Output is correct
56 Correct 95 ms 80296 KB Output is correct
57 Correct 124 ms 80156 KB Output is correct
58 Correct 28 ms 55908 KB Output is correct
59 Correct 27 ms 55152 KB Output is correct
60 Correct 26 ms 55124 KB Output is correct
61 Correct 131 ms 80196 KB Output is correct
62 Correct 27 ms 55872 KB Output is correct
63 Correct 173 ms 85248 KB Output is correct
64 Correct 130 ms 80148 KB Output is correct
65 Correct 27 ms 55916 KB Output is correct
66 Correct 145 ms 80336 KB Output is correct
67 Correct 30 ms 55936 KB Output is correct
68 Correct 30 ms 55892 KB Output is correct
69 Correct 100 ms 80260 KB Output is correct
70 Correct 29 ms 56012 KB Output is correct
71 Correct 114 ms 79836 KB Output is correct
72 Correct 181 ms 81552 KB Output is correct
73 Correct 30 ms 55116 KB Output is correct
74 Correct 143 ms 85340 KB Output is correct
75 Correct 142 ms 83780 KB Output is correct
76 Correct 28 ms 55892 KB Output is correct
77 Correct 29 ms 55892 KB Output is correct
78 Correct 96 ms 78996 KB Output is correct
79 Correct 196 ms 94292 KB Output is correct
80 Correct 30 ms 56144 KB Output is correct
81 Correct 33 ms 55864 KB Output is correct
82 Correct 26 ms 55124 KB Output is correct
83 Correct 29 ms 55072 KB Output is correct
84 Correct 30 ms 55788 KB Output is correct
85 Correct 147 ms 83300 KB Output is correct
86 Correct 28 ms 55852 KB Output is correct
87 Correct 123 ms 81036 KB Output is correct
88 Correct 27 ms 55156 KB Output is correct
89 Correct 136 ms 80588 KB Output is correct
90 Correct 164 ms 84548 KB Output is correct
91 Correct 251 ms 95820 KB Output is correct
92 Correct 94 ms 80272 KB Output is correct
93 Correct 29 ms 55968 KB Output is correct
94 Correct 26 ms 55096 KB Output is correct
95 Correct 185 ms 93296 KB Output is correct
96 Correct 251 ms 98356 KB Output is correct
97 Correct 29 ms 55884 KB Output is correct
98 Correct 26 ms 55124 KB Output is correct
99 Correct 124 ms 84368 KB Output is correct
100 Correct 28 ms 55976 KB Output is correct
101 Correct 142 ms 82488 KB Output is correct
102 Correct 266 ms 98124 KB Output is correct
103 Correct 29 ms 56276 KB Output is correct
104 Correct 30 ms 56396 KB Output is correct
105 Correct 32 ms 55892 KB Output is correct
106 Correct 28 ms 55888 KB Output is correct
107 Correct 27 ms 55992 KB Output is correct
108 Correct 760 ms 196888 KB Output is correct
109 Correct 1113 ms 191452 KB Output is correct
110 Correct 1020 ms 200116 KB Output is correct
111 Correct 1865 ms 262144 KB Output is correct
112 Correct 1502 ms 235352 KB Output is correct
113 Correct 1219 ms 239524 KB Output is correct
114 Correct 714 ms 174236 KB Output is correct
115 Correct 683 ms 174284 KB Output is correct
116 Correct 866 ms 180548 KB Output is correct
117 Correct 1861 ms 251408 KB Output is correct
118 Correct 739 ms 174772 KB Output is correct
119 Correct 1797 ms 250356 KB Output is correct
120 Runtime error 1838 ms 262144 KB Execution killed with signal 9
121 Halted 0 ms 0 KB -