Submission #707316

#	Time	Username	Problem	Language	Result	Execution time	Memory
707316		Danilo21	Mergers (JOI19_mergers)	C++17	100 / 100	1320 ms	235040 KiB

mergers

#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> comp, sz;
    vector<vector<int> > g;
    void dfs(int s, int c){
        if (this->comp[s] == c) return;
        this->comp[s] = c;
        for (int u : this->g[s])
            dfs(u, c);
    }
public:
    void init(int n){
        this->n = n;
        this->sz = vector<int>(n, 1);
        this->comp = vector<int>(n);
        for (int i = 0; i < n; i++) this->comp[i] = i;
        this->g = vector<vector<int> >(n);
    }
    void merge(int s, int u){
        if (comp[s] == comp[u]) return;
        this->g[s].pb(u);
        this->g[u].pb(s);
        if (this->sz[this->comp[s]] < this->sz[this->comp[u]]) swap(s, u);
        this->sz[this->comp[s]] += this->sz[this->comp[u]];
        this->sz[this->comp[u]] = 0;
        dfs(u, this->comp[s]);
    }
    int find(int s) const { return this->comp[s]; }
    int clean(){
        int mp[this->n];
        memset(mp, -1, sizeof(mp));
        int m = 0;
        for (int i = 0; i < this->n; i++)
            if (this->sz[this->comp[i]])
                if (!~mp[this->comp[i]])
                    mp[this->comp[i]] = m++;
        for (int i = 0; i < n; i++)
            this->comp[i] = mp[this->comp[i]];
        return m;
    }
};

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

void dfs(int s, int p){

    for (int u : tree.GetChilds(s)) sum[s] += sum[u];
    if (sum[s] && ~p) ds.merge(s, p);
}

void Solve(){

    cin >> n >> m;
    tree.Assign(n);
    tree.Read();
    tree.Initialize();
    memset(lca, -1, sizeof(lca));
    for (int i = 0; i < n; i++){
        cin >> a[i]; a[i]--;
        if (!~lca[a[i]]) lca[a[i]] = i;
        else lca[a[i]] = tree.Lca(lca[a[i]], i);
    }
    for (int i = 0; i < n; i++){
        sum[i]++; sum[lca[a[i]]]--;
    }
    ds.init(n);
    tree.Dfs(Empty, &dfs);
    ds.clean();
    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: 10 / 10
• Subtask 2: 24 / 24
• Subtask 3: 14 / 14
• Subtask 4: 22 / 22
• Subtask 5: 30 / 30