oj.uz

Submission #1094115

# Submission time Handle Problem Language Result Execution time Memory
1094115 2024-09-28T12:51:33 Z gyg Synchronization (JOI13_synchronization) C++17
20 / 100
 1533 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_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;
    // }
}

arr<int, 4 * MX_N> 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) {
    int dlt = -ind[u] + 1, sb_sz = fn_ind[u] + dlt;
    fill(sgtr.begin(), sgtr.begin() + 4 * sb_sz + 10, 0);

    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: In function 'void mdfy_frm(std::map<int, int>&, std::vector<std::pair<int, int> >&)':
synchronization.cpp:72: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]
   72 |     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:103: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]
  103 |     for (int i = 0; i < y.size(); i++) {
      |                     ~~^~~~~~~~~~
synchronization.cpp:106: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]
  106 |             if (i + 1 != y.size() && it->fir >= y[i + 1].fir) break;
      |                 ~~~~~~^~~~~~~~~~~
synchronization.cpp: In function 'void cmp(int)':
synchronization.cpp:210: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]
  210 |         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 17 ms 34908 KB Output is correct
2 Correct 17 ms 34688 KB Output is correct
3 Correct 15 ms 34908 KB Output is correct
4 Correct 16 ms 34908 KB Output is correct
5 Correct 16 ms 34808 KB Output is correct
6 Correct 21 ms 35932 KB Output is correct
7 Correct 94 ms 46500 KB Output is correct
8 Correct 85 ms 46420 KB Output is correct
9 Correct 89 ms 46928 KB Output is correct
10 Correct 1328 ms 162420 KB Output is correct
11 Correct 1263 ms 163188 KB Output is correct
12 Correct 1160 ms 201436 KB Output is correct
13 Correct 374 ms 111480 KB Output is correct
14 Correct 1449 ms 197560 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 821 ms 215872 KB Output is correct
2 Correct 793 ms 214076 KB Output is correct
3 Runtime error 731 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 17 ms 34908 KB Output is correct
2 Correct 17 ms 34908 KB Output is correct
3 Correct 17 ms 34904 KB Output is correct
4 Correct 17 ms 34908 KB Output is correct
5 Correct 18 ms 34852 KB Output is correct
6 Correct 23 ms 35940 KB Output is correct
7 Correct 109 ms 50092 KB Output is correct
8 Correct 1369 ms 202160 KB Output is correct
9 Correct 1318 ms 201948 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1341 ms 202200 KB Output is correct
2 Runtime error 811 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 17 ms 34908 KB Output is correct
2 Correct 17 ms 34908 KB Output is correct
3 Correct 16 ms 34904 KB Output is correct
4 Correct 18 ms 34908 KB Output is correct
5 Correct 24 ms 35932 KB Output is correct
6 Correct 99 ms 46692 KB Output is correct
7 Correct 1533 ms 165688 KB Output is correct
8 Correct 1367 ms 202148 KB Output is correct
9 Correct 449 ms 112640 KB Output is correct
10 Correct 1524 ms 199088 KB Output is correct
11 Correct 910 ms 217152 KB Output is correct
12 Correct 907 ms 217200 KB Output is correct
13 Runtime error 759 ms 262144 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -