oj.uz

Submission #794590

# Submission time Handle Problem Language Result Execution time Memory
794590 2023-07-26T15:59:04 Z Cookie Regions (IOI09_regions) C++14
55 / 100
 3517 ms 80028 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], -1}); 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 47216 KB Output is correct
2 Correct 24 ms 47192 KB Output is correct
3 Correct 24 ms 47224 KB Output is correct
4 Correct 25 ms 47268 KB Output is correct
5 Correct 26 ms 47312 KB Output is correct
6 Correct 35 ms 47312 KB Output is correct
7 Correct 41 ms 47312 KB Output is correct
8 Correct 54 ms 47412 KB Output is correct
9 Correct 67 ms 47820 KB Output is correct
10 Correct 94 ms 47752 KB Output is correct
11 Correct 112 ms 48072 KB Output is correct
12 Correct 148 ms 48616 KB Output is correct
13 Correct 123 ms 48184 KB Output is correct
14 Correct 272 ms 48848 KB Output is correct
15 Correct 249 ms 51324 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1792 ms 56684 KB Output isn't correct
2 Incorrect 2033 ms 55704 KB Output isn't correct
3 Incorrect 2705 ms 58900 KB Output isn't correct
4 Correct 270 ms 48948 KB Output is correct
5 Correct 361 ms 50512 KB Output is correct
6 Correct 1182 ms 50104 KB Output is correct
7 Correct 1430 ms 51236 KB Output is correct
8 Correct 1170 ms 56260 KB Output is correct
9 Correct 2065 ms 56680 KB Output is correct
10 Correct 3513 ms 61640 KB Output is correct
11 Correct 3517 ms 56488 KB Output is correct
12 Incorrect 1187 ms 68804 KB Output isn't correct
13 Incorrect 1858 ms 69032 KB Output isn't correct
14 Incorrect 2454 ms 71304 KB Output isn't correct
15 Incorrect 2706 ms 73584 KB Output isn't correct
16 Incorrect 2502 ms 78940 KB Output isn't correct
17 Incorrect 3105 ms 80028 KB Output isn't correct