oj.uz

Submission #1106888

# Submission time Handle Problem Language Result Execution time Memory
1106888 2024-10-31T08:43:46 Z Yang8on Regions (IOI09_regions) C++17
100 / 100
 2628 ms 54436 KB 
#include <bits/stdc++.h>
#define Y8o "REGIONS"
#define maxn (int) 2e5 + 5
#define ll long long
#define pii pair<int, int>
#define gb(i, j) ((i >> j) & 1)
#define all(x) x.begin(), x.end()
#define _left id * 2, l, mid
#define _right id * 2 + 1, mid + 1, r
#define fi(i, a, b) for(int i = a; i <= b; i ++)
#define fid(i, a, b) for(int i = a; i >= b; i --)

//#define f first
//#define s second

using namespace std;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll GetRandom(ll l, ll r) {
    return uniform_int_distribution<ll> (l, r) (rng);
}
void iof() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL), cout.tie(NULL);
    if(fopen(Y8o".inp", "r"))
    {
        freopen(Y8o".inp", "r", stdin);
//        freopen(Y8o".out", "w", stdout);
    }
}
void ctime() {
    cerr << "\n" << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
}

const int can = 450;

int n, m, Q, cnt;
int a[maxn];
int in[maxn], out[maxn], vir[maxn], dem[maxn];
vector<pii> cur, qq[maxn];
vector<int> o[maxn], pos[maxn];
vector<int> ans_dw[maxn], ans_up[maxn];

void pre_dfs(int u = 1) {
    in[u] = ++cnt;
    for(int v : o[u]) pre_dfs(v);
    out[u] = cnt;
    qq[a[u]].push_back({ in[u], out[u] });
}

void dfs(int u, int cl, int d) {
    ans_dw[cl][a[u]] += d;
    d += (dem[u] = (a[u] == cl));
    for(int v : o[u]) {
        dfs(v, cl, d);
        dem[u] += dem[v];
    }
    ans_up[cl][a[u]] += dem[u];
}

void solve() {
    cin >> n >> m >> Q;
    fi(i, 1, n) {
        if(i > 1) {
            int u; cin >> u;
            o[u].push_back(i);
        }
        cin >> a[i], pos[a[i]].push_back(i);
    }

    pre_dfs();

    cnt = 0;
    fi(i, 1, m) {
        if(pos[i].size() > can) {
            ans_up[i].assign(m + 1, 0);
            ans_dw[i].assign(m + 1, 0);
            dfs(1, i, 0);
        }
        sort( all(pos[i]), [&](int x, int y) { return in[x] < in[y]; });
    }

    fi(_, 1, Q) {
        int u, v; cin >> u >> v;
        if(pos[u].size() > can) cout << ans_dw[u][v] << endl;
        else if(pos[v].size() > can) cout << ans_up[v][u] << endl;
        else {
//            cur.clear();
//            fi(i, 0, pos[u].size() - 1) {
//                int node = pos[u][i];
//                cur.push_back({ in[node], +1 }), cur.push_back({ out[node] + 1, -1 });
//            }
//            sort(all(cur));
//
//            int j = 0, op = 0; ll res = 0;
//            fi(i, 0, pos[v].size() - 1) {
//                int node = pos[v][i];
//                while(j < cur.size() && cur[j].first <= in[node]) op += cur[j ++].second;
//                res += op;
//            }
//            cout << res << endl;

            int total=0,j=0;
            vector<pii> cc;
            for(auto [l,r]:qq[u]){
                while(j<(int)pos[v].size() && in[pos[v][j]]<=r) cc.push_back({pos[v][j++],1});
                while((int)cc.size()>=2 && in[cc.end()[-2].first]>=l){
                    int u=cc.back().second;cc.pop_back();
                    cc.back().second+=u;
                }
                if(!cc.empty() && in[cc.back().first]>=l) total+=cc.back().second;
            }
            cout << total << endl;
        }
    }
}


signed main() {
    iof();

    int nTest = 1;
//    cin >> nTest;

    while(nTest --) {
        solve();
    }

//    ctime();
    return 0;
}

Compilation message

regions.cpp: In function 'void iof()':
regions.cpp:27:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |         freopen(Y8o".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 27216 KB Output is correct
2 Correct 5 ms 27228 KB Output is correct
3 Correct 7 ms 27216 KB Output is correct
4 Correct 8 ms 27216 KB Output is correct
5 Correct 10 ms 27216 KB Output is correct
6 Correct 18 ms 27216 KB Output is correct
7 Correct 27 ms 27216 KB Output is correct
8 Correct 26 ms 27216 KB Output is correct
9 Correct 44 ms 27728 KB Output is correct
10 Correct 61 ms 27728 KB Output is correct
11 Correct 95 ms 27984 KB Output is correct
12 Correct 111 ms 28496 KB Output is correct
13 Correct 134 ms 28240 KB Output is correct
14 Correct 179 ms 28752 KB Output is correct
15 Correct 225 ms 31916 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 841 ms 32012 KB Output is correct
2 Correct 925 ms 30440 KB Output is correct
3 Correct 1615 ms 34400 KB Output is correct
4 Correct 239 ms 28876 KB Output is correct
5 Correct 318 ms 30544 KB Output is correct
6 Correct 592 ms 33324 KB Output is correct
7 Correct 993 ms 32060 KB Output is correct
8 Correct 883 ms 45468 KB Output is correct
9 Correct 1599 ms 36600 KB Output is correct
10 Correct 2112 ms 53696 KB Output is correct
11 Correct 2628 ms 35856 KB Output is correct
12 Correct 989 ms 37524 KB Output is correct
13 Correct 1305 ms 38220 KB Output is correct
14 Correct 1647 ms 40820 KB Output is correct
15 Correct 2091 ms 43860 KB Output is correct
16 Correct 2243 ms 52884 KB Output is correct
17 Correct 2145 ms 54436 KB Output is correct