oj.uz

Submission #1094111

# Submission time Handle Problem Language Result Execution time Memory
1094111 2024-09-28T12:45:01 Z gyg Synchronization (JOI13_synchronization) C++17
20 / 100
 1612 ms 262144 KB 
#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++) 
            if (frm[u].count(rv_ind[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 dlt = -ind[u] + 1, sb_sz = fn_ind[u] + dlt;

    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] + dlt, 1, sb_sz);
            i++;
        }
        ans[x.sec.fir] += qry(1, sb_sz, sb_sz);
        if (x.sec.sec != -1) ans[x.sec.fir] -= qry(ind[x.sec.sec] + dlt, fn_ind[x.sec.sec] + dlt, sb_sz);
    }
}

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

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:217: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]
  217 |         while (i != upds[u].size() && upds[u][i].fir <= x.fir) {
      |                ~~^~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 34904 KB Output is correct
2 Correct 16 ms 34904 KB Output is correct
3 Correct 17 ms 34852 KB Output is correct
4 Correct 16 ms 34908 KB Output is correct
5 Correct 17 ms 34908 KB Output is correct
6 Correct 25 ms 35932 KB Output is correct
7 Correct 96 ms 46676 KB Output is correct
8 Correct 93 ms 46416 KB Output is correct
9 Correct 108 ms 46928 KB Output is correct
10 Correct 1261 ms 163444 KB Output is correct
11 Correct 1256 ms 164248 KB Output is correct
12 Correct 1150 ms 202632 KB Output is correct
13 Correct 379 ms 111656 KB Output is correct
14 Correct 1450 ms 198132 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 844 ms 216640 KB Output is correct
2 Correct 786 ms 214848 KB Output is correct
3 Runtime error 738 ms 262144 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 35160 KB Output is correct
2 Correct 16 ms 34820 KB Output is correct
3 Correct 17 ms 34904 KB Output is correct
4 Correct 18 ms 34908 KB Output is correct
5 Correct 17 ms 34908 KB Output is correct
6 Correct 24 ms 35932 KB Output is correct
7 Correct 106 ms 50100 KB Output is correct
8 Correct 1282 ms 202968 KB Output is correct
9 Correct 1270 ms 202720 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1316 ms 202968 KB Output is correct
2 Runtime error 743 ms 262144 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 34904 KB Output is correct
2 Correct 15 ms 34892 KB Output is correct
3 Correct 15 ms 34764 KB Output is correct
4 Correct 15 ms 34904 KB Output is correct
5 Correct 21 ms 35808 KB Output is correct
6 Correct 98 ms 46704 KB Output is correct
7 Correct 1459 ms 165880 KB Output is correct
8 Correct 1309 ms 202920 KB Output is correct
9 Correct 486 ms 112744 KB Output is correct
10 Correct 1612 ms 200112 KB Output is correct
11 Correct 1002 ms 217128 KB Output is correct
12 Correct 922 ms 217136 KB Output is correct
13 Runtime error 787 ms 262144 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -