oj.uz

Submission #724401

# Submission time Handle Problem Language Result Execution time Memory
724401 2023-04-15T07:57:21 Z Magikarp4000 Regions (IOI09_regions) C++17
95 / 100
 4507 ms 131072 KB 
#include <bits/stdc++.h>
using namespace std;
#define OPTM ios_base::sync_with_stdio(0); cin.tie(0);
#define INF int(1e9+7)
#define ln '\n' 
#define ll long long
#define ull unsigned long long
#define ui unsigned int
#define us unsigned short
#define FOR(i,s,n) for (int i = s; i < n; i++)
#define FORR(i,n,s) for (int i = n; i > s; i--)
#define FORX(u, arr) for (auto u : arr)
#define PB push_back
#define in(v,x) (v.find(x) != v.end())
#define F first
#define S second
#define PII pair<int, int>
#define PLL pair<ll, ll>
#define UM unordered_map
#define US unordered_set
#define PQ priority_queue
#define ALL(v) v.begin(), v.end()
const ll LLINF = 1e18+1;

const int MAXN = 2e5+1, MAXR = 2.5e4+1;
int32_t n,r,q;
vector<int32_t> adj[MAXN];
vector<pair<int32_t,int32_t>> reg[MAXR];
int32_t h[MAXN];
vector<int32_t> emp[MAXR];
int32_t mp[MAXN], out[MAXN];
UM<int32_t,int32_t> pre[MAXR];
int timer;

void dfs(int s) {
    emp[h[s]].PB(s);
    mp[s] = timer;
    timer++;
    FORX(u,adj[s]) {
        dfs(u);
    }
    out[s] = timer;
}

int calc(int a, int b) {
    int i = 0, j = 0, res = 0;
    int an = reg[a].size(), bn = emp[b].size();
    while (i < an && j < bn) {
        if (reg[a][i].F < mp[emp[b][j]]) i++;
        else {
            res += reg[a][i].S;
            j++;
        }
    }
    return res;
}

signed main() {
    OPTM;
    cin >> n >> r >> q >> h[1];
    int blk = sqrt(n+.0)+1;
    FOR(i,2,n+1) {
        int x;
        cin >> x >> h[i];
        adj[x].PB(i);
    }
    dfs(1);
    FOR(i,1,r+1) {
        vector<PII> v;
        FORX(u,emp[i]) {
            v.PB({mp[u],1});
            v.PB({out[u],-1});
        }
        sort(ALL(v));
        int vn = v.size();
        int j = 0, cur = 0;
        while (j < vn) {
            if (v[j].F-1 >= 0) reg[i].PB({v[j].F-1,cur});
            cur += v[j].S;
            while (j+1 < vn && v[j+1].F == v[j].F) cur += v[++j].S;
            j++;
        }
        reg[i].PB({n-1,cur});
    }
    FOR(i,1,r+1) {
        if (emp[i].size() >= blk) {
            FOR(j,1,r+1) {
                if (i == j) continue;
                pre[i][j] = calc(i,j);
                pre[j][i] = calc(j,i);
            }
        }
    }
    FOR(_,0,q) {
        int a,b; cin >> a >> b;
        if (emp[a].size() >= blk || emp[b].size() >= blk) cout << pre[a][b];
        else cout << calc(a,b);
        cout << endl;
    }
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:86:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   86 |         if (emp[i].size() >= blk) {
      |             ~~~~~~~~~~~~~~^~~~~~
regions.cpp:96:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   96 |         if (emp[a].size() >= blk || emp[b].size() >= blk) cout << pre[a][b];
      |             ~~~~~~~~~~~~~~^~~~~~
regions.cpp:96:51: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   96 |         if (emp[a].size() >= blk || emp[b].size() >= blk) cout << pre[a][b];
      |                                     ~~~~~~~~~~~~~~^~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7508 KB Output is correct
2 Correct 5 ms 7504 KB Output is correct
3 Correct 7 ms 7504 KB Output is correct
4 Correct 8 ms 7504 KB Output is correct
5 Correct 11 ms 7504 KB Output is correct
6 Correct 15 ms 7632 KB Output is correct
7 Correct 25 ms 7632 KB Output is correct
8 Correct 40 ms 7632 KB Output is correct
9 Correct 52 ms 8144 KB Output is correct
10 Correct 47 ms 8144 KB Output is correct
11 Correct 108 ms 8528 KB Output is correct
12 Correct 122 ms 9036 KB Output is correct
13 Correct 145 ms 9040 KB Output is correct
14 Correct 208 ms 9732 KB Output is correct
15 Correct 239 ms 11856 KB Output is correct

Subtask #2
80.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 853 ms 13296 KB Output is correct
2 Correct 1256 ms 12400 KB Output is correct
3 Correct 1821 ms 15128 KB Output is correct
4 Correct 256 ms 9732 KB Output is correct
5 Correct 348 ms 11344 KB Output is correct
6 Correct 1297 ms 49988 KB Output is correct
7 Correct 1724 ms 52940 KB Output is correct
8 Correct 2543 ms 98260 KB Output is correct
9 Correct 1549 ms 19808 KB Output is correct
10 Runtime error 1746 ms 131072 KB Execution killed with signal 9
11 Correct 2566 ms 20364 KB Output is correct
12 Correct 2169 ms 25236 KB Output is correct
13 Correct 2493 ms 25288 KB Output is correct
14 Correct 4423 ms 57876 KB Output is correct
15 Correct 4049 ms 32172 KB Output is correct
16 Correct 3498 ms 35728 KB Output is correct
17 Correct 4507 ms 66108 KB Output is correct