oj.uz

Submission #649623

# Submission time Handle Problem Language Result Execution time Memory
649623 2022-10-11T07:02:17 Z mychecksedad Regions (IOI09_regions) C++17
65 / 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];

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;
            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;
        }
    }
}





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:80:16: warning: unused variable 'aa' [-Wunused-variable]
   80 |     int T = 1, aa;
      |                ^~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 70776 KB Output is correct
2 Correct 36 ms 70712 KB Output is correct
3 Correct 36 ms 70784 KB Output is correct
4 Correct 45 ms 70944 KB Output is correct
5 Correct 46 ms 71044 KB Output is correct
6 Correct 54 ms 72648 KB Output is correct
7 Correct 72 ms 72352 KB Output is correct
8 Correct 54 ms 73296 KB Output is correct
9 Correct 92 ms 78664 KB Output is correct
10 Correct 114 ms 89540 KB Output is correct
11 Correct 137 ms 88852 KB Output is correct
12 Correct 160 ms 109608 KB Output is correct
13 Correct 199 ms 105676 KB Output is correct
14 Correct 189 ms 97076 KB Output is correct
15 Correct 243 ms 115112 KB Output is correct

Subtask #2
50.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 95 ms 131072 KB Execution killed with signal 9
2 Runtime error 108 ms 131072 KB Execution killed with signal 9
3 Runtime error 89 ms 131072 KB Execution killed with signal 9
4 Correct 362 ms 73028 KB Output is correct
5 Correct 250 ms 74540 KB Output is correct
6 Correct 1430 ms 74688 KB Output is correct
7 Correct 1614 ms 76040 KB Output is correct
8 Correct 1580 ms 80980 KB Output is correct
9 Correct 2108 ms 82656 KB Output is correct
10 Correct 4909 ms 87260 KB Output is correct
11 Correct 3882 ms 85604 KB Output is correct
12 Correct 5409 ms 83856 KB Output is correct
13 Correct 6719 ms 84688 KB Output is correct
14 Execution timed out 8041 ms 85216 KB Time limit exceeded
15 Execution timed out 8064 ms 88464 KB Time limit exceeded
16 Execution timed out 8048 ms 93496 KB Time limit exceeded
17 Execution timed out 8038 ms 92532 KB Time limit exceeded