oj.uz

Submission #707313

# Submission time Handle Problem Language Result Execution time Memory
707313 2023-03-08T18:34:54 Z Danilo21 Mergers (JOI19_mergers) C++14
0 / 100
 210 ms 262144 KB 
#include <bits/stdc++.h>

#define ll long long
#define ld long double
#define pb push_back
#define fi first
#define se second
#define en '\n'
#define sp ' '
#define tb '\t'
#define ri(n) int n; cin >> n
#define rl(n) ll n; cin >> n
#define rs(s) string s; cin >> s
#define rc(c) char c; cin >> c
#define rv(v) for (auto &x : v) cin >> x
#define pven(v) for (auto x : v) cout << x << en
#define pv(v) for (auto x : v) cout << x << sp; cout << en
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define yes cout << "YES" << en
#define no cout << "NO" << en
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
#define ssort(a, b) if (a < b) swap(a, b)
#define bitcnt(a) (__builtin_popcountll(a))
#define bithigh(a) (63-__builtin_clzll(a))
#define lg bithigh
#define highpow(a) (1LL << (ll)lg(a))

using namespace std;

class Tree{

private:
    int n, root;
    vector<int> depth, in, out;
    vector<vector<int> > g, par;
    int _edges_ = 0;
    bool _initialized_ = 0;

    bool Valid(int s) const { return s >= 0 && s < n; }

    int InitDfs(int s, int p = -1, int d = 0, int t = 0){
        par[s][0] = p;
        depth[s] = d;
        in[s] = t;
        for (int u : g[s])
            if (u^p)
                t = InitDfs(u, s, d+1, t+1);
        return out[s] = ++t;
    }

    void Dfs(int s, int p, void bf(int, int), void af(int, int)) const {
        bf(s, p);
        for (int u : g[s])
            if (u^p)
                Dfs(u, s, bf, af);
        af(s, p);
    }

public:
    Tree(int n = 0){ Assign(n); }

    void Assign(int n = 0){
        this->n = n;
        depth.assign(n, 0);
        in.assign(n, 0);
        out.assign(n, 0);
        g.assign(n, vector<int>());
        par.assign(n, vector<int>(lg(n)+1, -1));
    }

    void Edge(int u, int v){
        if (!Valid(u) || !Valid(v)){
            cerr << "Node index out of range" << endl;
            exit(1);
        }
        g[u].pb(v);
        g[v].pb(u);
        _edges_++;
    }

    void Read(int d = 1){
        for (int i = 0; i < n-1; i++){
            ri(u); ri(v);
            u -= d; v -= d;
            Edge(u, v);
        }
    }

    void Initialize(int s = 0){
        if (!Valid(s)){
            cerr << "Node index out of range" << endl;
            exit(1);
        }
        if (_edges_ < n-1){
            cerr << "Tree is not connected" << endl;
            exit(1);
        }
        if (_edges_ > n-1){
            cerr << "Tree has cycle(s)" << endl;
            exit(1);
        }
        root = s;
        InitDfs(s);
        for (int d = 1; d <= lg(n); d++)
            for (int i = 0; i < n; i++)
                if (depth[i] >= (1<<d))
                    par[i][d] = par[par[i][d-1]][d-1];
        _initialized_ = 1;
    }

    int Size() const { return n; }

    int Depth(int s) const {
        if (!Valid(s)){
            cerr << "Node index out of range" << endl;
            exit(1);
        }
        return depth[s];
    }

    int InTime(int s) const {
        if (!Valid(s)){
            cerr << "Node index out of range" << endl;
            exit(1);
        }
        return in[s];
    }

    int OutTime(int s) const {
        if (!Valid(s)){
            cerr << "Node index out of range" << endl;
            exit(1);
        }
        return out[s];
    }

    vector<int> GetAdjecent(int s) const {
        if (!Valid(s)){
            cerr << "Node index out of range" << endl;
            exit(1);
        }
        return g[s];
    }

    vector<int> GetChilds(int s) const {
        if (!Valid(s)){
            cerr << "Node index out of range" << endl;
            exit(1);
        }
        vector<int> ch;
        for (int u : g[s])
            if (u^par[s][0])
                ch.pb(u);
        return ch;
    }

    int Par(int s, int d = 1) const {
        if (!_initialized_){
            cerr << "Tree has not been initialized yet" << endl;
            exit(1);
        }
        if (d < 0 || d > depth[s]) return -1;
        if (!d) return s;
        return Par(par[s][lg(d)], d - highpow(d));
    }

    bool Ancestor(int s, int p) const {
        if (!_initialized_){
            cerr << "Tree has not been initialized yet" << endl;
            exit(1);
        }
        return in[p] <= in[s] && out[p] >= out[s];
    }

    int Lca(int u, int v) const {
        if (!Valid(u) || !Valid(v)){
            cerr << "Node index out of range" << endl;
            exit(1);
        }
        if (!_initialized_){
            cerr << "Tree has not been initialized yet" << endl;
            exit(1);
        }
        if (depth[u] > depth[v]) swap(u, v);
        if (Ancestor(v, u)) return u;
        v = Par(v, depth[v] - depth[u]);
        for (int d = lg(n); ~d; d--){
            if (par[u][d] != par[v][d]){
                u = par[u][d];
                v = par[v][d];
            }
        }
        return par[u][0];
    }

    int Dist(int u, int v) const {
        if (!Valid(u) || !Valid(v)){
            cerr << "Node index out of range" << endl;
            exit(1);
        }
        if (!_initialized_){
            cerr << "Tree has not been initialized yet" << endl;
            exit(1);
        }
        int lca = Lca(u, v);
        return 2*depth[lca] - depth[u] - depth[v];
    }

    void Dfs(void bf(int, int), void af(int, int)) const { Dfs(root, -1, bf, af); }
};
#define Empty [](int, int){}

class dsu{
private:
    int n;
    vector<int> f;
public:
    void init(int n){
        this->n = n;
        f.resize(n);
        for (int i = 0; i < n; i++)
            f[i] = i;
    }
    void merge(int s, int u){ f[find(u)] = s; }
    int find(int s){
        if (f[s] == s) return s;
        return f[s] = find(f[s]);
    }
};

const ll LINF = 4e18;
const int mxN = 1e6+10, INF = 2e9;
ll n, m, a[mxN];
vector<int> v[mxN];
set<int> g[mxN];
Tree tree;
dsu ds;

void Solve(){

    cin >> n >> m;
    tree.Assign(n);
    tree.Read();
    tree.Initialize();
    for (int i = 0; i < n; i++){
        cin >> a[i]; a[i]--;
        v[a[i]].pb(i);
    }
    ds.init(n);
    for (int c = 0; c < m; c++){
        int s = v[c][0];
        for (int u : v[c]) s = tree.Lca(s, u);
        for (int u : v[c]){
            while (ds.find(u) != ds.find(s)){
                ds.merge(tree.Par(u), u);
                u = ds.find(u);
            }
        }
    }
    for (int s = 1; s < n; s++){
        if (ds.find(s) != ds.find(tree.Par(s))){
            g[ds.find(s)].insert(ds.find(tree.Par(s)));
            g[ds.find(tree.Par(s))].insert(ds.find(s));
        }
    }
    int cnt = 0;
    for (int s = 0; s < n; s++)
        if (g[s].size() == 1) cnt++;
    cout << (cnt+1)/2 << en;
}

int main(){

    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0); cerr.tie(0);
    cout << setprecision(12) << fixed;
    cerr << setprecision(12) << fixed;
    cerr << "Started!" << endl;

    int t = 1;
    //cin >> t;
    while (t--)
        Solve();

    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 70740 KB Output is correct
2 Correct 32 ms 70740 KB Output is correct
3 Correct 33 ms 70712 KB Output is correct
4 Correct 33 ms 70736 KB Output is correct
5 Correct 32 ms 70756 KB Output is correct
6 Correct 34 ms 70684 KB Output is correct
7 Correct 34 ms 70696 KB Output is correct
8 Correct 31 ms 70768 KB Output is correct
9 Correct 35 ms 70772 KB Output is correct
10 Correct 39 ms 70692 KB Output is correct
11 Correct 35 ms 70724 KB Output is correct
12 Correct 33 ms 70860 KB Output is correct
13 Correct 35 ms 70752 KB Output is correct
14 Correct 33 ms 70680 KB Output is correct
15 Runtime error 154 ms 262144 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 70740 KB Output is correct
2 Correct 32 ms 70740 KB Output is correct
3 Correct 33 ms 70712 KB Output is correct
4 Correct 33 ms 70736 KB Output is correct
5 Correct 32 ms 70756 KB Output is correct
6 Correct 34 ms 70684 KB Output is correct
7 Correct 34 ms 70696 KB Output is correct
8 Correct 31 ms 70768 KB Output is correct
9 Correct 35 ms 70772 KB Output is correct
10 Correct 39 ms 70692 KB Output is correct
11 Correct 35 ms 70724 KB Output is correct
12 Correct 33 ms 70860 KB Output is correct
13 Correct 35 ms 70752 KB Output is correct
14 Correct 33 ms 70680 KB Output is correct
15 Runtime error 154 ms 262144 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 70740 KB Output is correct
2 Correct 32 ms 70740 KB Output is correct
3 Correct 33 ms 70712 KB Output is correct
4 Correct 33 ms 70736 KB Output is correct
5 Correct 32 ms 70756 KB Output is correct
6 Correct 34 ms 70684 KB Output is correct
7 Correct 34 ms 70696 KB Output is correct
8 Correct 31 ms 70768 KB Output is correct
9 Correct 35 ms 70772 KB Output is correct
10 Correct 39 ms 70692 KB Output is correct
11 Correct 35 ms 70724 KB Output is correct
12 Correct 33 ms 70860 KB Output is correct
13 Correct 35 ms 70752 KB Output is correct
14 Correct 33 ms 70680 KB Output is correct
15 Runtime error 154 ms 262144 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 89728 KB Output is correct
2 Correct 127 ms 101700 KB Output is correct
3 Correct 42 ms 71460 KB Output is correct
4 Correct 34 ms 71244 KB Output is correct
5 Correct 33 ms 70684 KB Output is correct
6 Correct 33 ms 70732 KB Output is correct
7 Correct 35 ms 71272 KB Output is correct
8 Runtime error 210 ms 262144 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 70740 KB Output is correct
2 Correct 32 ms 70740 KB Output is correct
3 Correct 33 ms 70712 KB Output is correct
4 Correct 33 ms 70736 KB Output is correct
5 Correct 32 ms 70756 KB Output is correct
6 Correct 34 ms 70684 KB Output is correct
7 Correct 34 ms 70696 KB Output is correct
8 Correct 31 ms 70768 KB Output is correct
9 Correct 35 ms 70772 KB Output is correct
10 Correct 39 ms 70692 KB Output is correct
11 Correct 35 ms 70724 KB Output is correct
12 Correct 33 ms 70860 KB Output is correct
13 Correct 35 ms 70752 KB Output is correct
14 Correct 33 ms 70680 KB Output is correct
15 Runtime error 154 ms 262144 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -