oj.uz

Submission #794592

# Submission time Handle Problem Language Result Execution time Memory
794592 2023-07-26T16:01:19 Z Cookie Regions (IOI09_regions) C++14
55 / 100
 3660 ms 79912 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], 2});
                        
            } 
        }
    }
    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 23 ms 47184 KB Output is correct
2 Correct 25 ms 47196 KB Output is correct
3 Correct 30 ms 47184 KB Output is correct
4 Correct 28 ms 47312 KB Output is correct
5 Correct 30 ms 47244 KB Output is correct
6 Correct 40 ms 47364 KB Output is correct
7 Correct 43 ms 47268 KB Output is correct
8 Correct 43 ms 47364 KB Output is correct
9 Correct 64 ms 47824 KB Output is correct
10 Correct 84 ms 47824 KB Output is correct
11 Correct 80 ms 48016 KB Output is correct
12 Correct 134 ms 48576 KB Output is correct
13 Correct 148 ms 48200 KB Output is correct
14 Correct 255 ms 48868 KB Output is correct
15 Correct 249 ms 51408 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1860 ms 56684 KB Output isn't correct
2 Incorrect 2135 ms 55716 KB Output isn't correct
3 Incorrect 2805 ms 58892 KB Output isn't correct
4 Correct 262 ms 48976 KB Output is correct
5 Correct 326 ms 50512 KB Output is correct
6 Correct 1316 ms 50184 KB Output is correct
7 Correct 1321 ms 51172 KB Output is correct
8 Correct 1075 ms 56268 KB Output is correct
9 Correct 1973 ms 56644 KB Output is correct
10 Correct 3660 ms 61700 KB Output is correct
11 Correct 3613 ms 56476 KB Output is correct
12 Incorrect 1076 ms 68840 KB Output isn't correct
13 Incorrect 1876 ms 68924 KB Output isn't correct
14 Incorrect 2763 ms 71404 KB Output isn't correct
15 Incorrect 2962 ms 73512 KB Output isn't correct
16 Incorrect 2627 ms 78988 KB Output isn't correct
17 Incorrect 2707 ms 79912 KB Output isn't correct