oj.uz

Submission #649638

# Submission time Handle Problem Language Result Execution time Memory
649638 2022-10-11T07:29:53 Z mychecksedad Regions (IOI09_regions) C++17
30 / 100
 5380 ms 105468 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], path, pos[N];
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);
    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;
            if(R[a].size() < R[b].size())
                for(int v: R[a]){
                    ans += upper_bound(all(pos[b]), tout[v]) - upper_bound(all(pos[b]), tin[v]);
                }
            else
                for(int v: R[b]){
                    ans += int(pos[a].size()) - (upper_bound(all(pos[a]), tout[v]) - upper_bound(all(pos[a]), 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:67:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |         for(int j = 0; j < path.size(); ++j){
      |                        ~~^~~~~~~~~~~~~
regions.cpp: In function 'int main()':
regions.cpp:97:16: warning: unused variable 'aa' [-Wunused-variable]
   97 |     int T = 1, aa;
      |                ^~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 70736 KB Output is correct
2 Correct 44 ms 70812 KB Output is correct
3 Correct 36 ms 70732 KB Output is correct
4 Correct 47 ms 70772 KB Output is correct
5 Correct 42 ms 70864 KB Output is correct
6 Correct 52 ms 71376 KB Output is correct
7 Correct 63 ms 71260 KB Output is correct
8 Correct 70 ms 71260 KB Output is correct
9 Correct 88 ms 71832 KB Output is correct
10 Correct 120 ms 74312 KB Output is correct
11 Correct 145 ms 72676 KB Output is correct
12 Correct 163 ms 72788 KB Output is correct
13 Correct 177 ms 88392 KB Output is correct
14 Correct 186 ms 75740 KB Output is correct
15 Correct 208 ms 75756 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 843 ms 77832 KB Output is correct
2 Correct 662 ms 102636 KB Output is correct
3 Correct 1271 ms 77572 KB Output is correct
4 Incorrect 303 ms 74668 KB Output isn't correct
5 Incorrect 458 ms 76620 KB Output isn't correct
6 Incorrect 596 ms 76732 KB Output isn't correct
7 Incorrect 993 ms 77208 KB Output isn't correct
8 Incorrect 1287 ms 85040 KB Output isn't correct
9 Incorrect 2342 ms 90964 KB Output isn't correct
10 Incorrect 5380 ms 97208 KB Output isn't correct
11 Incorrect 4652 ms 97224 KB Output isn't correct
12 Incorrect 1331 ms 89120 KB Output isn't correct
13 Incorrect 2141 ms 91872 KB Output isn't correct
14 Incorrect 2383 ms 93616 KB Output isn't correct
15 Incorrect 3961 ms 99612 KB Output isn't correct
16 Incorrect 4099 ms 105468 KB Output isn't correct
17 Incorrect 3761 ms 104024 KB Output isn't correct