oj.uz

Submission #794588

# Submission time Handle Problem Language Result Execution time Memory
794588 2023-07-26T15:56:36 Z Cookie Regions (IOI09_regions) C++14
55 / 100
 3653 ms 131072 KB 
#include<bits/stdc++.h>
#include<fstream>
using namespace std;
 
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
const ld PI = 3.14159265359;
const ll mod = 1e9 + 7;
const int mxn = 5e5 + 5, mxm = 1e5, sq = 800;
const ld inf = 1e9;
int n, r, q, root;
int colour[mxn + 1], tin[mxn + 1], tout[mxn + 1], tt = 0, cnt[mxn + 1];
vt<int>vec[mxn + 1], adj[mxn + 1], to[mxn + 1];
vt<ll>ansb[mxn + 1];
void dfs(int s, int pre){
    tin[s] = ++tt;
    for(auto i: adj[s]){
        if(i != pre){
            dfs(i, s);
        }
    }
    tout[s] = tt;
}
struct th{
    int id, pos, type;
    bool operator <(const th &b){
        if(pos != b.pos)return(pos < b.pos);
        if(type != b.type)return(type < b.type);
        return(id > b.id);
    }
};
 
void solvebig(int i){
    vt<th>comp;
    for(auto k: vec[i]){
        comp.pb({0, tin[k], -1}); comp.pb({0, tout[k],1});
    }
    for(int j = 1; j <= r; j++){
        if(j != i){
           for(auto k: vec[j]){
                comp.pb({k, tin[k], -1}); comp.pb({k, tout[k], 1});
                        
            } 
        }
    }
    sort(comp.begin(), comp.end());
    ll cnt =0 ;
    for(auto [id, pos, type]: comp){
        if(id == 0){
            if(type == 1)cnt++;
            else cnt--;
        }else{
            if(type == 1)ansb[i][id] -= cnt;
            else ansb[i][id] += cnt;
        }
    }
    
    
}
signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> r >> q;
    cin >> colour[1];
    vec[colour[1]].pb(1);
    for(int i = 2; i <= n; i++){
        int p;
        cin >> p >> colour[i]; cnt[colour[i]]++;
        vec[colour[i]].pb(i); adj[p].pb(i);
    }
    dfs(1, -1);
    for(int i = 1; i <= r; i++){
        for(auto j: vec[i]){
            to[i].pb(tin[j]);
        }
        sort(to[i].begin(), to[i].end());
    }
    for(int i = 1; i <= r; i++){
        if(cnt[i] >= sq){
            ansb[i].resize(r + 1);
            solvebig(i);
        }
    }
    while(q--){
        int r1, r2; cin >> r1 >> r2;
        if(cnt[r1] >= sq){
            cout << ansb[r1][r2] << endl;
        }else{
            ll ans = 0;
            for(auto i: vec[r1]){
                
                int idl = lower_bound(to[r2].begin(), to[r2].end(), tin[i]) - to[r2].begin();
                int idr = upper_bound(to[r2].begin(), to[r2].end(), tout[i]) - to[r2].begin() - 1;
                ans += 1LL * (idr - idl + 1);
            }
            cout << ans << endl;
        }
    }
    return(0);
}

Compilation message

regions.cpp: In function 'void solvebig(int)':
regions.cpp:57:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   57 |     for(auto [id, pos, type]: comp){
      |              ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 47240 KB Output is correct
2 Correct 22 ms 47204 KB Output is correct
3 Correct 23 ms 47268 KB Output is correct
4 Correct 26 ms 47312 KB Output is correct
5 Correct 29 ms 47312 KB Output is correct
6 Correct 33 ms 47332 KB Output is correct
7 Correct 49 ms 47312 KB Output is correct
8 Correct 40 ms 47344 KB Output is correct
9 Correct 52 ms 47732 KB Output is correct
10 Correct 80 ms 47816 KB Output is correct
11 Correct 103 ms 48092 KB Output is correct
12 Correct 114 ms 48544 KB Output is correct
13 Correct 189 ms 48272 KB Output is correct
14 Correct 236 ms 48752 KB Output is correct
15 Correct 179 ms 51408 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 96 ms 108888 KB Execution killed with signal 11
2 Runtime error 104 ms 106736 KB Execution killed with signal 11
3 Runtime error 112 ms 113220 KB Execution killed with signal 11
4 Correct 276 ms 48932 KB Output is correct
5 Correct 279 ms 50504 KB Output is correct
6 Correct 1069 ms 50120 KB Output is correct
7 Correct 1481 ms 51224 KB Output is correct
8 Correct 1085 ms 56260 KB Output is correct
9 Correct 1754 ms 56748 KB Output is correct
10 Correct 3570 ms 61640 KB Output is correct
11 Correct 3653 ms 56488 KB Output is correct
12 Runtime error 179 ms 126972 KB Execution killed with signal 11
13 Runtime error 176 ms 127208 KB Execution killed with signal 11
14 Runtime error 190 ms 127872 KB Execution killed with signal 11
15 Runtime error 180 ms 131072 KB Execution killed with signal 11
16 Runtime error 171 ms 131072 KB Execution killed with signal 11
17 Runtime error 174 ms 131072 KB Execution killed with signal 11