oj.uz

Submission #649645

# Submission time Handle Problem Language Result Execution time Memory
649645 2022-10-11T07:39:35 Z mychecksedad Regions (IOI09_regions) C++17
100 / 100
 4750 ms 58940 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 = 2e5+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 10 ms 19032 KB Output is correct
2 Correct 10 ms 19024 KB Output is correct
3 Correct 12 ms 19124 KB Output is correct
4 Correct 13 ms 19152 KB Output is correct
5 Correct 15 ms 19152 KB Output is correct
6 Correct 26 ms 19664 KB Output is correct
7 Correct 33 ms 19536 KB Output is correct
8 Correct 38 ms 19664 KB Output is correct
9 Correct 39 ms 20176 KB Output is correct
10 Correct 81 ms 22672 KB Output is correct
11 Correct 111 ms 20924 KB Output is correct
12 Correct 153 ms 21140 KB Output is correct
13 Correct 127 ms 36736 KB Output is correct
14 Correct 148 ms 24152 KB Output is correct
15 Correct 160 ms 24016 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 622 ms 26164 KB Output is correct
2 Correct 951 ms 50972 KB Output is correct
3 Correct 1139 ms 25896 KB Output is correct
4 Correct 312 ms 23336 KB Output is correct
5 Correct 307 ms 25704 KB Output is correct
6 Correct 673 ms 25888 KB Output is correct
7 Correct 708 ms 26448 KB Output is correct
8 Correct 1093 ms 35416 KB Output is correct
9 Correct 1985 ms 40952 KB Output is correct
10 Correct 3694 ms 49092 KB Output is correct
11 Correct 4750 ms 47840 KB Output is correct
12 Correct 1228 ms 39204 KB Output is correct
13 Correct 2118 ms 42368 KB Output is correct
14 Correct 2885 ms 43988 KB Output is correct
15 Correct 4387 ms 51124 KB Output is correct
16 Correct 3823 ms 58940 KB Output is correct
17 Correct 2929 ms 56916 KB Output is correct