oj.uz

Submission #649622

# Submission time Handle Problem Language Result Execution time Memory
649622 2022-10-11T06:57:43 Z mychecksedad Regions (IOI09_regions) C++17
15 / 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 << 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 34 ms 70720 KB Output is correct
2 Correct 33 ms 70700 KB Output is correct
3 Correct 36 ms 70860 KB Output is correct
4 Correct 37 ms 70844 KB Output is correct
5 Correct 40 ms 70988 KB Output is correct
6 Correct 49 ms 72676 KB Output is correct
7 Correct 52 ms 72392 KB Output is correct
8 Correct 68 ms 73300 KB Output is correct
9 Correct 78 ms 78552 KB Output is correct
10 Correct 132 ms 89544 KB Output is correct
11 Correct 142 ms 88856 KB Output is correct
12 Correct 173 ms 109728 KB Output is correct
13 Correct 133 ms 105776 KB Output is correct
14 Correct 187 ms 97076 KB Output is correct
15 Correct 191 ms 115092 KB Output is correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 89 ms 131072 KB Execution killed with signal 9
2 Runtime error 97 ms 131072 KB Execution killed with signal 9
3 Runtime error 93 ms 131072 KB Execution killed with signal 9
4 Incorrect 321 ms 73124 KB Output isn't correct
5 Incorrect 381 ms 74500 KB Output isn't correct
6 Incorrect 1393 ms 74688 KB Output isn't correct
7 Incorrect 1672 ms 76128 KB Output isn't correct
8 Incorrect 1390 ms 81032 KB Output isn't correct
9 Incorrect 2359 ms 82744 KB Output isn't correct
10 Incorrect 4848 ms 87192 KB Output isn't correct
11 Incorrect 4035 ms 85612 KB Output isn't correct
12 Incorrect 5171 ms 83912 KB Output isn't correct
13 Incorrect 5834 ms 84688 KB Output isn't correct
14 Incorrect 7610 ms 85228 KB Output isn't correct
15 Execution timed out 8015 ms 88412 KB Time limit exceeded
16 Execution timed out 8069 ms 93408 KB Time limit exceeded
17 Execution timed out 8066 ms 92536 KB Time limit exceeded