Submission #1094110

#	Time	Username	Problem	Language	Result	Execution time	Memory
1094110		gyg	Synchronization (JOI13_synchronization)	C++17	0 / 100	867 ms	262144 KiB

synchronization

#include <bits/stdc++.h>
using namespace std;
#define arr array
#define vct vector
#define pii pair<int, int>
#define fir first 
#define sec second
#define mpii make_pair
#define lb lower_bound
#define ub upper_bound
#define hmap unordered_map
const int MX_N = 1e5 + 5, INF = 1e9;

int n, m, q;
arr<vct<pii>, MX_N> adj;
arr<vct<pii>, MX_N> rngs;

arr<bool, MX_N> dltd;
arr<int, MX_N> sz;
void cmp_szs(int u, int pr = -1) {
    sz[u] = 1;
    for (pii x : adj[u]) {
        if (dltd[x.fir] || x.fir == pr) continue;
        cmp_szs(x.fir, u);
        sz[u] += sz[x.fir];
    }
}
int gt_cnt(int u, int whl_sz, int pr = -1) {
    for (pii x : adj[u]) {
        if (dltd[x.fir] || x.fir == pr) continue;
        if (2 * sz[x.fir] > whl_sz) return gt_cnt(x.fir, whl_sz, u);
    }
    return u;
}
arr<int, MX_N> cnt_pr; 
void cmp_prs(int u, int cnt, int pr = -1) {
    if (u != cnt) cnt_pr[u] = cnt;
    for (pii x : adj[u]) {
        if (dltd[x.fir] || x.fir == pr) continue;
        cmp_prs(x.fir, cnt, u);
    }
}

arr<int, MX_N> dsu_pr;
arr<vct<int>, MX_N> fmly;
int gt_pr(int u) {
    if (dsu_pr[u] == u) return u;
    dsu_pr[u] = gt_pr(dsu_pr[u]);
    return dsu_pr[u];
}
void mrg_fmly(int u, int v) {
    u = gt_pr(u), v = gt_pr(v);
    assert(u != v);
    if (fmly[u].size() < fmly[v].size()) swap(u, v);
    for (int x : fmly[v]) fmly[u].push_back(x);
    dsu_pr[v] = u;
}

arr<map<int, int>, MX_N> frm_mp, twrd_mp;
void mrg_it(map<int, vct<int>>& x, auto& it1, auto& it2) {
    int vl = it1->fir;
    if (it1->sec.size() < it2->sec.size()) swap(it1, it2);
    for (int y : it2->sec) it1->sec.push_back(y);
    x.erase(it2);
    it1->fir = vl;
}
void mrg_mp(map<int, int>& x, map<int, int>& y) {
    if (x.size() < y.size()) x.swap(y);
    for (pii z : y) {
        if (x.count(z.fir)) mrg_fmly(x[z.fir], z.sec);
        else x.insert(z);
    }
}

void mdfy_frm(map<int, int>& x, vct<pii>& y) {
    int lst = (y.size()) ? y.back().sec : -1;
    while (x.size() && x.rbegin()->fir > lst) x.erase(next(x.end(), -1));

    for (int i = 0; i < y.size(); i++) {
        vct<int> cmb;
        if (x.lb(y[i].fir) == x.begin()) continue;
        for (auto it = next(x.lb(y[i].fir), -1); ; it--) {
            if (i != 0 && it->fir <= y[i - 1].sec) break;
            cmb.push_back(it->fir);
            if (it == x.begin()) break;
        }
        int u = (x.count(y[i].fir)) ? x[y[i].fir] : -1;
        for (int z : cmb) {
            if (u == -1) u = x[z];
            else mrg_fmly(u, x[z]);
            x.erase(z);
        }
        if (u != -1) x[y[i].fir] = u;
    }
}
void cmp_frms(int u, int pr = -1) {
    dsu_pr[u] = u, fmly[u] = {u};
    frm_mp[u] = {{1, u}};
    for (pii x : adj[u]) {
        if (dltd[x.fir] || x.fir == pr) continue;
        cmp_frms(x.fir, u);
        mdfy_frm(frm_mp[x.fir], rngs[x.sec]);
        mrg_mp(frm_mp[u], frm_mp[x.fir]);
    }
}
void mdfy_twrd(map<int, int>& x, vct<pii>& y) {
    int frst = (y.size()) ? y[0].fir : INF;
    while (x.size() && x.begin()->fir < frst) x.erase(x.begin());

    for (int i = 0; i < y.size(); i++) {
        vct<int> cmb;
        for (auto it = x.ub(y[i].sec); it != x.end(); it++) {
            if (i + 1 != y.size() && it->fir >= y[i + 1].fir) break;
            cmb.push_back(it->fir);
        }
        int u = (x.count(y[i].sec)) ? x[y[i].sec] : -1;
        for (int z : cmb) {
            if (u == -1) u = x[z];
            else mrg_fmly(u, x[z]);
            x.erase(z);
        }
        if (u != -1) x[y[i].sec] = u;
    }
}
void cmp_twrds(int u, int pr = -1) {
    dsu_pr[u] = u, fmly[u] = {u};
    twrd_mp[u] = {{m, u}};
    for (pii x : adj[u]) {
        if (dltd[x.fir] || x.fir == pr) continue;
        cmp_twrds(x.fir, u);
        mdfy_twrd(twrd_mp[x.fir], rngs[x.sec]);
        mrg_mp(twrd_mp[u], twrd_mp[x.fir]);
    }
}

arr<hmap<int, int>, MX_N> frm, twrd;
void bld(int u = 1) {
    cmp_szs(u);
    int cnt = gt_cnt(u, sz[u]);

    cmp_prs(cnt, cnt);
    cmp_frms(cnt);
    for (pii x : frm_mp[cnt])
        for (int y : fmly[gt_pr(x.sec)]) frm[cnt][y] = x.fir; 
    cmp_twrds(cnt);
    for (pii x : twrd_mp[cnt])
        for (int y : fmly[gt_pr(x.sec)]) twrd[cnt][y] = x.fir; 

    
    // cout << cnt << ": ";
    // // for (pii x : frm[cnt]) cout << x.fir << "," << x.sec << " ";
    // for (pii x : twrd[cnt]) cout << x.fir << "," << x.sec << " ";
    // cout << endl;
    
    dltd[cnt] = true;
    for (pii x : adj[cnt])
        if (!dltd[x.fir]) bld(x.fir);
}

arr<vct<int>, MX_N> chldrn;
int nm_inds;
arr<int, MX_N> ind, fn_ind, rv_ind;
void cmp_inds(int u) {
    nm_inds++, ind[u] = nm_inds, rv_ind[nm_inds] = u;
    for (int v : chldrn[u]) cmp_inds(v);
    fn_ind[u] = nm_inds;
}
arr<vct<pair<int, pii>>, MX_N> qrys;
arr<vct<pii>, MX_N> upds;
void prcmp() {
    bld();    
    for (int u = 1; u <= n; u++) chldrn[cnt_pr[u]].push_back(u);
    for (int u = 1; u <= n; u++)
        if (cnt_pr[u] == 0) { cmp_inds(u); break; }
    for (int u = 1; u <= n; u++) {
        for (int i = ind[u]; i <= fn_ind[u]; i++) upds[u].push_back({frm[u][rv_ind[i]], rv_ind[i]});
        int lst = -1, v = u;
        while (v != 0) {
            qrys[v].push_back({twrd[v][u], {u, lst}});
            lst = v, v = cnt_pr[v];
        }
    }
    for (int u = 1; u <= n; u++) 
        sort(upds[u].begin(), upds[u].end()), sort(qrys[u].begin(), qrys[u].end());

    // for (int u = 1; u <= n; u++) {
    //     cout << u << ": ";
    //     // for (pii x : upds[u]) cout << x.sec << "," << x.fir << " ";
    //     for (pair<int, pii> x : qrys[u]) cout << x.sec.fir << "," << x.sec.sec << "," << x.fir << " ";
    //     cout << endl;
    // }
}

vct<int> sgtr;
void upd(int i, int x, int hg, int lw = 1, int u = 1) {
    if (i < lw || hg < i) return;
    if (lw == hg) { sgtr[u] += x; return; }
    int md = (lw + hg) / 2;
    upd(i, x, md, lw, 2 * u), upd(i, x, hg, md + 1, 2 * u + 1);
    sgtr[u] = sgtr[2 * u] + sgtr[2 * u + 1];
}
int qry(int l, int r, int hg, int lw = 1, int u = 1) {
    if (r < lw || hg < l) return 0;
    if (l <= lw && hg <= r) return sgtr[u];
    int md = (lw + hg) / 2;
    return qry(l, r, md, lw, 2 * u) + qry(l, r, hg, md + 1, 2 * u + 1);
}

arr<int, MX_N> ans;
void cmp(int u) {
    sgtr.clear(), sgtr.resize(4 * (fn_ind[u] - ind[u]) + 10);
    int i = 0;
    for (pair<int, pii> x : qrys[u]) {
        while (i != upds[u].size() && upds[u][i].fir <= x.fir) {
            upd(ind[upds[u][i].sec] - ind[u] + 1, 1, fn_ind[u] - ind[u] + 1);
            i++;
        }
        ans[x.sec.fir] += qry(1, fn_ind[u] - ind[u] + 1, fn_ind[u] - ind[u] + 1);
        if (x.sec.sec != -1) ans[x.sec.fir] -= qry(ind[x.sec.sec] - ind[u] + 1, fn_ind[x.sec.sec] - ind[u] + 1, fn_ind[u] - ind[u] + 1);
    }
}

int main() {
    // freopen("sync.in", "r", stdin);
    cin >> n >> m >> q;
    for (int i = 1; i <= n - 1; i++) {
        int u, v; cin >> u >> v;
        adj[u].push_back({v, i}), adj[v].push_back({u, i});
    }
    for (int i = 1; i <= m; i++) {
        int j; cin >> j;
        if (rngs[j].empty() || rngs[j].back().sec != 0) rngs[j].push_back({i, 0});
        else rngs[j].back().sec = i - 1;
    }
    for (int i = 1; i <= n - 1; i++)
        if (rngs[i].size() && rngs[i].back().sec == 0) rngs[i].back().sec = m;

    prcmp();
    for (int u = 1; u <= n; u++) cmp(u);

    for (int i = 1; i <= q; i++) {
        int u; cin >> u;
        cout << ans[u] << endl;
    }
}

Compilation message (stderr)

synchronization.cpp:60:36: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   60 | void mrg_it(map<int, vct<int>>& x, auto& it1, auto& it2) {
      |                                    ^~~~
synchronization.cpp:60:47: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   60 | void mrg_it(map<int, vct<int>>& x, auto& it1, auto& it2) {
      |                                               ^~~~
synchronization.cpp: In function 'void mdfy_frm(std::map<int, int>&, std::vector<std::pair<int, int> >&)':
synchronization.cpp:79:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |     for (int i = 0; i < y.size(); i++) {
      |                     ~~^~~~~~~~~~
synchronization.cpp: In function 'void mdfy_twrd(std::map<int, int>&, std::vector<std::pair<int, int> >&)':
synchronization.cpp:110:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |     for (int i = 0; i < y.size(); i++) {
      |                     ~~^~~~~~~~~~
synchronization.cpp:113:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |             if (i + 1 != y.size() && it->fir >= y[i + 1].fir) break;
      |                 ~~~~~~^~~~~~~~~~~
synchronization.cpp: In function 'void cmp(int)':
synchronization.cpp:214:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  214 |         while (i != upds[u].size() && upds[u][i].fir <= x.fir) {
      |                ~~^~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 10
• Subtask 4: 0 / 20
• Subtask 5: 0 / 40