oj.uz

Submission #724399

# Submission time Handle Problem Language Result Execution time Memory
724399 2023-04-15T07:47:05 Z Magikarp4000 Regions (IOI09_regions) C++17
95 / 100
 5387 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>> v[MAXR], reg[MAXR];
int32_t h[MAXN];
vector<int32_t> tour;
vector<int32_t> emp[MAXR];
int32_t mp[MAXN];
UM<int32_t,int32_t> pre[MAXR];
int timer;

void dfs(int s) {
    tour.PB(s);
    emp[h[s]].PB(s);
    v[h[s]].PB({timer,1});
    timer++;
    FORX(u,adj[s]) {
        dfs(u);
    }
    v[h[s]].PB({timer,-1});
}

int calc(int a, int b) {
    int i = 0, j = 0, res = 0;
    while (i < reg[a].size() && j < emp[b].size()) {
        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,0,n) mp[tour[i]] = i;
    FOR(i,1,r+1) {
        sort(ALL(v[i]));
        int vn = v[i].size();
        int j = 0, j1 = 0, cur = 0;
        while (j < vn) {
            if (v[i][j].F-1 >= 0) reg[i].PB({v[i][j].F-1,cur});
            cur += v[i][j].S;
            while (j+1 < vn && v[i][j+1].F == v[i][j].F) cur += v[i][++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 calc(int, int)':
regions.cpp:49:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     while (i < reg[a].size() && j < emp[b].size()) {
      |            ~~^~~~~~~~~~~~~~~
regions.cpp:49:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     while (i < reg[a].size() && j < emp[b].size()) {
      |                                 ~~^~~~~~~~~~~~~~~
regions.cpp: In function 'int main()':
regions.cpp:73:20: warning: unused variable 'j1' [-Wunused-variable]
   73 |         int j = 0, j1 = 0, cur = 0;
      |                    ^~
regions.cpp:83:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   83 |         if (emp[i].size() >= blk) {
      |             ~~~~~~~~~~~~~~^~~~~~
regions.cpp:93:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   93 |         if (emp[a].size() >= blk || emp[b].size() >= blk) cout << pre[a][b];
      |             ~~~~~~~~~~~~~~^~~~~~
regions.cpp:93:51: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   93 |         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 8144 KB Output is correct
2 Correct 4 ms 8108 KB Output is correct
3 Correct 10 ms 8144 KB Output is correct
4 Correct 8 ms 8144 KB Output is correct
5 Correct 18 ms 8144 KB Output is correct
6 Correct 21 ms 8248 KB Output is correct
7 Correct 27 ms 8272 KB Output is correct
8 Correct 33 ms 8272 KB Output is correct
9 Correct 49 ms 8912 KB Output is correct
10 Correct 85 ms 9040 KB Output is correct
11 Correct 117 ms 9552 KB Output is correct
12 Correct 184 ms 10320 KB Output is correct
13 Correct 134 ms 10200 KB Output is correct
14 Correct 170 ms 11288 KB Output is correct
15 Correct 223 ms 14704 KB Output is correct

Subtask #2
80.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1035 ms 15780 KB Output is correct
2 Correct 1174 ms 14508 KB Output is correct
3 Correct 1688 ms 18516 KB Output is correct
4 Correct 265 ms 11228 KB Output is correct
5 Correct 367 ms 13404 KB Output is correct
6 Correct 1400 ms 51732 KB Output is correct
7 Correct 1640 ms 55268 KB Output is correct
8 Correct 2813 ms 102944 KB Output is correct
9 Correct 1697 ms 24864 KB Output is correct
10 Runtime error 1856 ms 131072 KB Execution killed with signal 9
11 Correct 2991 ms 25412 KB Output is correct
12 Correct 2253 ms 29608 KB Output is correct
13 Correct 2865 ms 30228 KB Output is correct
14 Correct 5085 ms 62624 KB Output is correct
15 Correct 5387 ms 39136 KB Output is correct
16 Correct 4139 ms 45876 KB Output is correct
17 Correct 5114 ms 76072 KB Output is correct