oj.uz

Submission #711801

# Submission time Handle Problem Language Result Execution time Memory
711801 2023-03-17T14:23:59 Z lukameladze Mergers (JOI19_mergers) C++14
0 / 100
 87 ms 34168 KB 
# include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
//#define int long long
#define pii pair <int, int>
#define pb push_back
const int N = 3e5 + 5;
int t,n,a[N],sz[N],tin,in[N],out[N],p[N],par[N][20],k,x[N],lv[N],deg[N];
vector <int> v[N];
vector <pii> vec[N];
void dfs(int a, int p) {
    tin++;
    in[a] = tin;
    par[a][0] = p;
    for (int i = 1; i <= 18; i++) {
        if (par[a][i - 1]) par[a][i] = par[par[a][i - 1]][i - 1];
    }
    lv[a] = lv[p] + 1;
    for (int to : v[a]) {
        if (to == p) continue;
        dfs(to, a);
    }
    out[a] = tin;
}
void init() {
    for (int i = 1; i <= n; i++) {
        p[i] = i; sz[i] = 1;
    }
}
int get_col(int a) {
    if (a == p[a]) return a;
    else return p[a] = get_col(p[a]); 
}
void col(int a, int b) {
    a = get_col(a); b = get_col(b);
    if (a == b) return ;
    if (lv[a] > lv[b]) swap(a, b);
    p[b] = a;
}
void merge(int a, int lc) {
    while (get_col(a) != get_col(lc)) {
        col(a, par[get_col(a)][0]);
    }
}
int upper(int a, int b) {
    return (in[a] <= in[b] && out[a] >= out[b]);
}
int lca(int a, int b) {
    if (upper(a, b)) return a;
    for (int i = 18; i >= 0; i--) {
        if (par[a][i] && !upper(par[a][i], b)) a = par[a][i];
    }
    return par[a][0];
}
main() {
    std::ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>k;
    vector <pii> edges;
    for (int i = 1; i <= n - 1; i++) {
        int a, b;
        cin>>a>>b;
        v[a].pb(b);
        v[b].pb(a);
        edges.pb({a,b});
    }
    dfs(1, 0);
    for (int i = 1; i <= n; i++) {
        cin>>x[i];
    }
    init();
    for (int i = 1; i <= n; i++) {
        vec[x[i]].pb({in[i], i});
    }
    for (int i = 1; i <= k; i++) {
        for (int j = 0; j < vec[i].size(); j++) {
            int a = vec[i][j].s, b = vec[i][(j + 1) % vec[i].size()].s, lc = lca(a, b);
            merge(a, lc); merge(b, lc);
        }
    }
    for (pii sth : edges) {
        if (get_col(sth.f) != get_col(sth.s)) {
            deg[sth.f]++; deg[sth.s]++;
        }
    }
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        cnt += (int)(deg[i] == 1);
    }
    cout<<(cnt + 1) / 2<<"\n";
}

Compilation message

mergers.cpp:56:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   56 | main() {
      | ^~~~
mergers.cpp: In function 'int main()':
mergers.cpp:76:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |         for (int j = 0; j < vec[i].size(); j++) {
      |                         ~~^~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 8 ms 14476 KB Output is correct
3 Incorrect 8 ms 14420 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 8 ms 14476 KB Output is correct
3 Incorrect 8 ms 14420 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 8 ms 14476 KB Output is correct
3 Incorrect 8 ms 14420 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 31436 KB Output is correct
2 Correct 85 ms 34168 KB Output is correct
3 Incorrect 10 ms 14932 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 8 ms 14476 KB Output is correct
3 Incorrect 8 ms 14420 KB Output isn't correct
4 Halted 0 ms 0 KB -