oj.uz

Submission #794585

# Submission time Handle Problem Language Result Execution time Memory
794585 2023-07-26T15:54:31 Z Cookie Regions (IOI09_regions) C++14
55 / 100
 3757 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);
        if(id != b.id)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] << "\n";
        }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){
      |              ^
regions.cpp: In member function 'bool th::operator<(const th&)':
regions.cpp:39:5: warning: control reaches end of non-void function [-Wreturn-type]
   39 |     }
      |     ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47192 KB Output is correct
2 Correct 22 ms 47252 KB Output is correct
3 Correct 24 ms 47304 KB Output is correct
4 Correct 27 ms 47276 KB Output is correct
5 Correct 30 ms 47280 KB Output is correct
6 Correct 36 ms 47336 KB Output is correct
7 Correct 43 ms 47336 KB Output is correct
8 Correct 50 ms 47292 KB Output is correct
9 Correct 54 ms 47720 KB Output is correct
10 Correct 96 ms 47824 KB Output is correct
11 Correct 93 ms 48120 KB Output is correct
12 Correct 116 ms 48592 KB Output is correct
13 Correct 153 ms 48200 KB Output is correct
14 Correct 239 ms 48848 KB Output is correct
15 Correct 229 ms 51396 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 96 ms 108932 KB Execution killed with signal 11
2 Runtime error 96 ms 106692 KB Execution killed with signal 11
3 Runtime error 104 ms 113184 KB Execution killed with signal 11
4 Correct 265 ms 48976 KB Output is correct
5 Correct 272 ms 50500 KB Output is correct
6 Correct 1315 ms 50128 KB Output is correct
7 Correct 1277 ms 51216 KB Output is correct
8 Correct 990 ms 56264 KB Output is correct
9 Correct 2211 ms 56648 KB Output is correct
10 Correct 3757 ms 61656 KB Output is correct
11 Correct 3569 ms 56516 KB Output is correct
12 Runtime error 169 ms 126824 KB Execution killed with signal 11
13 Runtime error 158 ms 127296 KB Execution killed with signal 11
14 Runtime error 170 ms 127832 KB Execution killed with signal 11
15 Runtime error 196 ms 131072 KB Execution killed with signal 11
16 Runtime error 180 ms 131072 KB Execution killed with signal 11
17 Runtime error 176 ms 131072 KB Execution killed with signal 11