oj.uz

Submission #649629

# Submission time Handle Problem Language Result Execution time Memory
649629 2022-10-11T07:18:40 Z mychecksedad Regions (IOI09_regions) C++17
73 / 100
 8000 ms 131080 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[5000][5000], 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(505);
    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
13.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 70800 KB Output is correct
2 Correct 33 ms 70864 KB Output is correct
3 Correct 34 ms 70856 KB Output is correct
4 Correct 38 ms 71248 KB Output is correct
5 Correct 38 ms 71876 KB Output is correct
6 Correct 54 ms 73680 KB Output is correct
7 Correct 57 ms 74508 KB Output is correct
8 Correct 60 ms 75712 KB Output is correct
9 Correct 89 ms 82844 KB Output is correct
10 Correct 89 ms 93412 KB Output is correct
11 Correct 138 ms 102544 KB Output is correct
12 Correct 172 ms 114120 KB Output is correct
13 Correct 204 ms 121192 KB Output is correct
14 Runtime error 80 ms 131072 KB Execution killed with signal 9
15 Runtime error 65 ms 131072 KB Execution killed with signal 9

Subtask #2
60.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 81 ms 131072 KB Execution killed with signal 9
2 Runtime error 87 ms 131072 KB Execution killed with signal 9
3 Runtime error 112 ms 131080 KB Execution killed with signal 9
4 Correct 328 ms 74584 KB Output is correct
5 Correct 435 ms 76760 KB Output is correct
6 Correct 626 ms 76720 KB Output is correct
7 Correct 863 ms 77356 KB Output is correct
8 Correct 1389 ms 85152 KB Output is correct
9 Correct 2357 ms 90992 KB Output is correct
10 Correct 4527 ms 97176 KB Output is correct
11 Correct 4238 ms 97396 KB Output is correct
12 Correct 4587 ms 89068 KB Output is correct
13 Correct 6149 ms 92044 KB Output is correct
14 Correct 6409 ms 93576 KB Output is correct
15 Execution timed out 8023 ms 98204 KB Time limit exceeded
16 Execution timed out 8010 ms 103576 KB Time limit exceeded
17 Correct 7479 ms 103828 KB Output is correct