oj.uz

Submission #1106885

# Submission time Handle Problem Language Result Execution time Memory
1106885 2024-10-31T08:37:20 Z Yang8on Regions (IOI09_regions) C++17
80 / 100
 5140 ms 131072 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 = 160;

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 4 ms 27216 KB Output is correct
2 Correct 4 ms 27216 KB Output is correct
3 Correct 6 ms 27216 KB Output is correct
4 Correct 10 ms 27216 KB Output is correct
5 Correct 9 ms 27216 KB Output is correct
6 Correct 18 ms 27216 KB Output is correct
7 Correct 26 ms 27216 KB Output is correct
8 Correct 32 ms 27216 KB Output is correct
9 Correct 34 ms 27728 KB Output is correct
10 Correct 69 ms 27728 KB Output is correct
11 Correct 94 ms 27984 KB Output is correct
12 Correct 121 ms 28508 KB Output is correct
13 Correct 131 ms 28240 KB Output is correct
14 Correct 194 ms 28828 KB Output is correct
15 Correct 225 ms 32584 KB Output is correct

Subtask #2
65.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 958 ms 32252 KB Output is correct
2 Correct 1008 ms 30580 KB Output is correct
3 Correct 1369 ms 34848 KB Output is correct
4 Correct 240 ms 29748 KB Output is correct
5 Correct 338 ms 30544 KB Output is correct
6 Correct 573 ms 33328 KB Output is correct
7 Correct 883 ms 36828 KB Output is correct
8 Correct 939 ms 45588 KB Output is correct
9 Correct 1783 ms 48620 KB Output is correct
10 Runtime error 1163 ms 131072 KB Execution killed with signal 9
11 Runtime error 2457 ms 131072 KB Execution killed with signal 9
12 Correct 5140 ms 112692 KB Output is correct
13 Correct 4014 ms 113384 KB Output is correct
14 Correct 4658 ms 116920 KB Output is correct
15 Runtime error 1975 ms 131072 KB Execution killed with signal 9
16 Runtime error 1768 ms 131072 KB Execution killed with signal 9
17 Correct 3481 ms 130544 KB Output is correct