oj.uz

Submission #649624

# Submission time Handle Problem Language Result Execution time Memory
649624 2022-10-11T07:08:44 Z mychecksedad Regions (IOI09_regions) C++17
70 / 100
 8000 ms 131072 KB 
/* Author : Mychecksdead */
#include<bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long int ll;
typedef long double ld;
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define PI 3.1415926535
#define pb push_back
#define setp() cout << setprecision(15)
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " is " << x << '\n';
const int N = 1e6+100, M = 1e5+10, F = 2147483646, K = 20;


int n, q, r, a[N], ans[1000][1000], tin[N], tout[N], timer = 0;
vector<int> g[N], R[N], path, pos[N];
map<pair<int, int>, pair<bool, int>> m;
void dfs(int v, int p){
    R[v].resize(r + 5);
    for(int u: g[v]){
        if(u == p) continue;
        dfs(u, v);
        for(int j = 1; j <= r; ++j) R[v][j] += R[u][j];
    }
    for(int j = 1; j <= r; ++j) ans[a[v]][j] += R[v][j];
    R[v][a[v]]++;    
}
void dfs1(int v, int p){
    path.pb(v);
    tin[v] = timer++;
    R[a[v]].pb(v);
    for(int u: g[v]){
        if(u == p) continue;
        dfs1(u, v);
    }
    path.pb(v);
    tout[v] = timer++;
}

void solve(){
    cin >> n >> r >> q;
    cin >> a[1];
    for(int i = 2; i <= n; ++i){
        int x; cin >> x >> a[i];
        g[x].pb(i);
        g[i].pb(x);
    }
    if(r <= 500){
        for(int i = 0; i <= r; ++i) for(int j = 0; j <= r; ++j) ans[i][j] = 0;
        dfs(1, 1);
        for(;q--;){
            int a, b; cin >> a >> b;
            cout << ans[a][b] << endl;
        }
    }else{
        dfs1(1, 1);
        for(int j = 0; j < path.size(); ++j){
            pos[a[path[j]]].pb(j);
        }
        for(;q--;){
            int a, b; cin >> a >> b;
            if(m[{a, b}].first){
                cout << m[{a, b}].second << endl;
                continue;
            }
            int ans = 0;
            for(int v: R[a]){
                ans += upper_bound(all(pos[b]), tout[v]) - upper_bound(all(pos[b]), tin[v]);
            }
            cout << ans/2 << endl;
            m[{a, b}] = {1, ans/2};
        }
    }
}





int main(){
    cin.tie(0); ios::sync_with_stdio(0);
    int T = 1, aa;
    // cin >> T;aa=T;
    while(T--){
        // cout << "Case #" << aa-T << ": ";
        solve();
        // cout << '\n';
    }
    return 0;
 
}

Compilation message

regions.cpp: In function 'void solve()':
regions.cpp:60:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |         for(int j = 0; j < path.size(); ++j){
      |                        ~~^~~~~~~~~~~~~
regions.cpp: In function 'int main()':
regions.cpp:85:16: warning: unused variable 'aa' [-Wunused-variable]
   85 |     int T = 1, aa;
      |                ^~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 70736 KB Output is correct
2 Correct 37 ms 70728 KB Output is correct
3 Correct 37 ms 70816 KB Output is correct
4 Correct 38 ms 70864 KB Output is correct
5 Correct 46 ms 70992 KB Output is correct
6 Correct 58 ms 72648 KB Output is correct
7 Correct 60 ms 72372 KB Output is correct
8 Correct 68 ms 73252 KB Output is correct
9 Correct 76 ms 78548 KB Output is correct
10 Correct 120 ms 89540 KB Output is correct
11 Correct 167 ms 88856 KB Output is correct
12 Correct 164 ms 109608 KB Output is correct
13 Correct 174 ms 105672 KB Output is correct
14 Correct 211 ms 97104 KB Output is correct
15 Correct 213 ms 115116 KB Output is correct

Subtask #2
55.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 95 ms 131072 KB Execution killed with signal 9
2 Runtime error 113 ms 131072 KB Execution killed with signal 9
3 Runtime error 96 ms 131072 KB Execution killed with signal 9
4 Correct 286 ms 74616 KB Output is correct
5 Correct 405 ms 76676 KB Output is correct
6 Correct 439 ms 76832 KB Output is correct
7 Correct 575 ms 77468 KB Output is correct
8 Correct 1514 ms 85140 KB Output is correct
9 Correct 2744 ms 91000 KB Output is correct
10 Correct 5222 ms 97272 KB Output is correct
11 Correct 4180 ms 97456 KB Output is correct
12 Correct 5758 ms 89208 KB Output is correct
13 Correct 6206 ms 91916 KB Output is correct
14 Correct 7264 ms 93812 KB Output is correct
15 Execution timed out 8013 ms 98596 KB Time limit exceeded
16 Execution timed out 8066 ms 102976 KB Time limit exceeded
17 Execution timed out 8068 ms 103908 KB Time limit exceeded