oj.uz

Submission #649625

# Submission time Handle Problem Language Result Execution time Memory
649625 2022-10-11T07:12:13 Z mychecksedad Regions (IOI09_regions) C++17
60 / 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;
        }
        cout << "bruh";
    }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:61:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |         for(int j = 0; j < path.size(); ++j){
      |                        ~~^~~~~~~~~~~~~
regions.cpp: In function 'int main()':
regions.cpp:86:16: warning: unused variable 'aa' [-Wunused-variable]
   86 |     int T = 1, aa;
      |                ^~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 41 ms 70732 KB Execution killed with signal 13
2 Runtime error 36 ms 70816 KB Execution killed with signal 13
3 Runtime error 43 ms 70768 KB Execution killed with signal 13
4 Runtime error 39 ms 70928 KB Execution killed with signal 13
5 Runtime error 42 ms 71072 KB Execution killed with signal 13
6 Runtime error 48 ms 72656 KB Execution killed with signal 13
7 Runtime error 58 ms 72424 KB Execution killed with signal 13
8 Runtime error 66 ms 73288 KB Execution killed with signal 13
9 Runtime error 83 ms 78556 KB Execution killed with signal 13
10 Runtime error 103 ms 89616 KB Execution killed with signal 13
11 Runtime error 141 ms 88864 KB Execution killed with signal 13
12 Runtime error 159 ms 109640 KB Execution killed with signal 13
13 Runtime error 206 ms 105676 KB Execution killed with signal 13
14 Runtime error 195 ms 97004 KB Execution killed with signal 13
15 Runtime error 248 ms 115208 KB Execution killed with signal 13

Subtask #2
60.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 140 ms 131072 KB Execution killed with signal 9
2 Runtime error 145 ms 131072 KB Execution killed with signal 9
3 Runtime error 112 ms 131072 KB Execution killed with signal 9
4 Correct 403 ms 74676 KB Output is correct
5 Correct 533 ms 76676 KB Output is correct
6 Correct 677 ms 76708 KB Output is correct
7 Correct 876 ms 77492 KB Output is correct
8 Correct 1320 ms 85488 KB Output is correct
9 Correct 2290 ms 91004 KB Output is correct
10 Correct 4346 ms 97232 KB Output is correct
11 Correct 3911 ms 97496 KB Output is correct
12 Correct 4614 ms 89116 KB Output is correct
13 Correct 5540 ms 91932 KB Output is correct
14 Correct 7158 ms 93548 KB Output is correct
15 Execution timed out 8035 ms 97760 KB Time limit exceeded
16 Execution timed out 8029 ms 104152 KB Time limit exceeded
17 Correct 7938 ms 104084 KB Output is correct