oj.uz

Submission #649641

# Submission time Handle Problem Language Result Execution time Memory
649641 2022-10-11T07:34:38 Z mychecksedad Regions (IOI09_regions) C++17
30 / 100
 4276 ms 130972 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, posin[N], posout[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){
            posin[a[path[j]]].pb(j);
            posout[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(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: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:98:16: warning: unused variable 'aa' [-Wunused-variable]
   98 |     int T = 1, aa;
      |                ^~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 94152 KB Output is correct
2 Correct 47 ms 94244 KB Output is correct
3 Correct 45 ms 94192 KB Output is correct
4 Correct 48 ms 94220 KB Output is correct
5 Correct 45 ms 94344 KB Output is correct
6 Correct 61 ms 94796 KB Output is correct
7 Correct 62 ms 94740 KB Output is correct
8 Correct 61 ms 94752 KB Output is correct
9 Correct 83 ms 95368 KB Output is correct
10 Correct 79 ms 97888 KB Output is correct
11 Correct 151 ms 96072 KB Output is correct
12 Correct 116 ms 96328 KB Output is correct
13 Correct 202 ms 111900 KB Output is correct
14 Correct 208 ms 99312 KB Output is correct
15 Correct 205 ms 99272 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 680 ms 101324 KB Output is correct
2 Correct 744 ms 126120 KB Output is correct
3 Correct 1205 ms 101064 KB Output is correct
4 Incorrect 328 ms 98464 KB Output isn't correct
5 Incorrect 379 ms 100552 KB Output isn't correct
6 Incorrect 691 ms 100780 KB Output isn't correct
7 Incorrect 942 ms 101716 KB Output isn't correct
8 Incorrect 1134 ms 109632 KB Output isn't correct
9 Incorrect 2476 ms 116524 KB Output isn't correct
10 Incorrect 3907 ms 123044 KB Output isn't correct
11 Incorrect 4276 ms 123248 KB Output isn't correct
12 Incorrect 1625 ms 114544 KB Output isn't correct
13 Incorrect 2111 ms 117420 KB Output isn't correct
14 Incorrect 2475 ms 119728 KB Output isn't correct
15 Incorrect 3204 ms 125596 KB Output isn't correct
16 Incorrect 4034 ms 130972 KB Output isn't correct
17 Incorrect 3360 ms 129976 KB Output isn't correct