oj.uz

Submission #649643

# Submission time Handle Problem Language Result Execution time Memory
649643 2022-10-11T07:37:07 Z mychecksedad Regions (IOI09_regions) C++17
90 / 100
 3972 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[505][505], tin[N], tout[N], timer = 0;
vector<int> g[N], R[N], posin[N], posout[N];
vector<pair<int, int>> path;
map<pair<int, int>, pair<bool, int>> m;
void dfs(int v, int p){
    bool ok = 1;
    for(int u: g[v]){
        if(u == p) continue;
        dfs(u, v);
        if(ok){
            ok = 0;
            R[v].swap(R[u]);
            continue;
        }
        for(int j = 1; j <= r; ++j) R[v][j] += R[u][j];
        R[u].clear();
    }
    if(ok) R[v].resize(r + 1);
    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, 1});
    tin[v] = timer++;
    R[a[v]].pb(v);
    for(int u: g[v]){
        if(u == p) continue;
        dfs1(u, v);
    }
    path.pb({v, 0});
    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){
            if(path[j].second == 1)
                posin[a[path[j].first]].pb(j);
            else
                posout[a[path[j].first]].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;
            if(R[a].size() < R[b].size())
                for(int v: R[a]){
                    ans += upper_bound(all(posin[b]), tout[v]) - upper_bound(all(posin[b]), tin[v]);
                }
            else
                for(int v: R[b]){
                    ans += (upper_bound(all(posin[a]), tin[v]) - posin[a].begin()) - (upper_bound(all(posout[a]), tin[v]) - posout[a].begin());
                }
            cout << ans << endl;
            m[{a, b}] = {1, ans};
        }
    }
}





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

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 94152 KB Output is correct
2 Correct 47 ms 94224 KB Output is correct
3 Correct 49 ms 94216 KB Output is correct
4 Correct 51 ms 94276 KB Output is correct
5 Correct 51 ms 94372 KB Output is correct
6 Correct 67 ms 94756 KB Output is correct
7 Correct 72 ms 94672 KB Output is correct
8 Correct 70 ms 94756 KB Output is correct
9 Correct 89 ms 95352 KB Output is correct
10 Correct 134 ms 97752 KB Output is correct
11 Correct 152 ms 96156 KB Output is correct
12 Correct 204 ms 96280 KB Output is correct
13 Correct 188 ms 111892 KB Output is correct
14 Correct 169 ms 99308 KB Output is correct
15 Correct 223 ms 99196 KB Output is correct

Subtask #2
75.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 699 ms 101324 KB Output is correct
2 Correct 1076 ms 126164 KB Output is correct
3 Correct 1107 ms 101064 KB Output is correct
4 Correct 298 ms 98536 KB Output is correct
5 Correct 395 ms 100852 KB Output is correct
6 Correct 742 ms 100768 KB Output is correct
7 Correct 1031 ms 101612 KB Output is correct
8 Correct 1361 ms 110640 KB Output is correct
9 Correct 2098 ms 116292 KB Output is correct
10 Correct 3810 ms 124136 KB Output is correct
11 Correct 3972 ms 123232 KB Output is correct
12 Correct 1270 ms 114716 KB Output is correct
13 Correct 2229 ms 117372 KB Output is correct
14 Correct 1991 ms 119348 KB Output is correct
15 Correct 2955 ms 126536 KB Output is correct
16 Runtime error 2418 ms 131072 KB Execution killed with signal 9
17 Runtime error 2896 ms 131072 KB Execution killed with signal 9