oj.uz

Submission #794593

# Submission time Handle Problem Language Result Execution time Memory
794593 2023-07-26T16:01:50 Z Cookie Regions (IOI09_regions) C++14
55 / 100
 3719 ms 79868 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({j, tin[k], -2}); comp.pb({j, 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 26 ms 47176 KB Output is correct
2 Correct 26 ms 47260 KB Output is correct
3 Correct 23 ms 47236 KB Output is correct
4 Correct 30 ms 47252 KB Output is correct
5 Correct 24 ms 47260 KB Output is correct
6 Correct 49 ms 47340 KB Output is correct
7 Correct 56 ms 47420 KB Output is correct
8 Correct 51 ms 47488 KB Output is correct
9 Correct 54 ms 47780 KB Output is correct
10 Correct 95 ms 47776 KB Output is correct
11 Correct 103 ms 48072 KB Output is correct
12 Correct 135 ms 48516 KB Output is correct
13 Correct 170 ms 48188 KB Output is correct
14 Correct 260 ms 48848 KB Output is correct
15 Correct 241 ms 51420 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1635 ms 56732 KB Output isn't correct
2 Incorrect 1870 ms 55724 KB Output isn't correct
3 Incorrect 2777 ms 58964 KB Output isn't correct
4 Correct 261 ms 48904 KB Output is correct
5 Correct 345 ms 50512 KB Output is correct
6 Correct 1168 ms 50124 KB Output is correct
7 Correct 1680 ms 51176 KB Output is correct
8 Correct 1092 ms 56168 KB Output is correct
9 Correct 2195 ms 56716 KB Output is correct
10 Correct 3719 ms 61672 KB Output is correct
11 Correct 3586 ms 56524 KB Output is correct
12 Incorrect 1250 ms 68848 KB Output isn't correct
13 Incorrect 1822 ms 69108 KB Output isn't correct
14 Incorrect 2694 ms 71336 KB Output isn't correct
15 Incorrect 2760 ms 73556 KB Output isn't correct
16 Incorrect 2637 ms 78932 KB Output isn't correct
17 Incorrect 2975 ms 79868 KB Output isn't correct