oj.uz

Submission #649627

# Submission time Handle Problem Language Result Execution time Memory
649627 2022-10-11T07:14:55 Z mychecksedad Regions (IOI09_regions) C++17
60 / 100
 8000 ms 104016 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[1000][1000], 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(r + 5);
    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){
        cout << "bruh"; return;
        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:61:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |         for(int j = 0; j < path.size(); ++j){
      |                        ~~^~~~~~~~~~~~~
regions.cpp: In function 'int main()':
regions.cpp:86:16: warning: unused variable 'aa' [-Wunused-variable]
   86 |     int T = 1, aa;
      |                ^~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 33 ms 70768 KB Expected integer, but "bruh" found
2 Incorrect 33 ms 70652 KB Expected integer, but "bruh" found
3 Incorrect 35 ms 70888 KB Expected integer, but "bruh" found
4 Incorrect 34 ms 70736 KB Expected integer, but "bruh" found
5 Incorrect 34 ms 70692 KB Expected integer, but "bruh" found
6 Incorrect 39 ms 70724 KB Expected integer, but "bruh" found
7 Incorrect 33 ms 70824 KB Expected integer, but "bruh" found
8 Incorrect 36 ms 70780 KB Expected integer, but "bruh" found
9 Incorrect 35 ms 70912 KB Expected integer, but "bruh" found
10 Incorrect 39 ms 71020 KB Expected integer, but "bruh" found
11 Incorrect 36 ms 71188 KB Expected integer, but "bruh" found
12 Incorrect 38 ms 71368 KB Expected integer, but "bruh" found
13 Incorrect 45 ms 71532 KB Expected integer, but "bruh" found
14 Incorrect 44 ms 71740 KB Expected integer, but "bruh" found
15 Incorrect 43 ms 72136 KB Expected integer, but "bruh" found

Subtask #2
60.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 53 ms 73392 KB Expected integer, but "bruh" found
2 Incorrect 51 ms 73572 KB Expected integer, but "bruh" found
3 Incorrect 61 ms 73944 KB Expected integer, but "bruh" found
4 Correct 330 ms 74628 KB Output is correct
5 Correct 472 ms 76784 KB Output is correct
6 Correct 607 ms 76720 KB Output is correct
7 Correct 1115 ms 77404 KB Output is correct
8 Correct 1538 ms 85016 KB Output is correct
9 Correct 3014 ms 90992 KB Output is correct
10 Correct 5362 ms 97404 KB Output is correct
11 Correct 3988 ms 97292 KB Output is correct
12 Correct 4691 ms 89168 KB Output is correct
13 Correct 6234 ms 92024 KB Output is correct
14 Correct 6934 ms 93684 KB Output is correct
15 Execution timed out 8092 ms 98640 KB Time limit exceeded
16 Execution timed out 8063 ms 103060 KB Time limit exceeded
17 Correct 7821 ms 104016 KB Output is correct