oj.uz

Submission #794599

# Submission time Handle Problem Language Result Execution time Memory
794599 2023-07-26T16:09:39 Z Cookie Regions (IOI09_regions) C++14
30 / 100
 8000 ms 127084 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 = 0;
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 == -2)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 25 ms 47312 KB Output is correct
2 Correct 23 ms 47312 KB Output is correct
3 Correct 23 ms 47240 KB Output is correct
4 Correct 25 ms 47220 KB Output is correct
5 Correct 31 ms 47312 KB Output is correct
6 Correct 61 ms 47932 KB Output is correct
7 Correct 75 ms 47624 KB Output is correct
8 Correct 108 ms 47816 KB Output is correct
9 Correct 232 ms 48916 KB Output is correct
10 Correct 761 ms 49852 KB Output is correct
11 Correct 733 ms 49436 KB Output is correct
12 Correct 1628 ms 51604 KB Output is correct
13 Correct 1527 ms 50592 KB Output is correct
14 Correct 1129 ms 50712 KB Output is correct
15 Correct 1330 ms 54360 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 3226 ms 57156 KB Output is correct
2 Correct 3729 ms 56108 KB Output is correct
3 Correct 4902 ms 59432 KB Output is correct
4 Execution timed out 8042 ms 99432 KB Time limit exceeded
5 Execution timed out 8052 ms 102744 KB Time limit exceeded
6 Execution timed out 8053 ms 99484 KB Time limit exceeded
7 Execution timed out 8077 ms 103392 KB Time limit exceeded
8 Execution timed out 8068 ms 97840 KB Time limit exceeded
9 Execution timed out 8095 ms 97200 KB Time limit exceeded
10 Execution timed out 8100 ms 118404 KB Time limit exceeded
11 Execution timed out 8048 ms 107188 KB Time limit exceeded
12 Execution timed out 8055 ms 94668 KB Time limit exceeded
13 Execution timed out 8052 ms 95260 KB Time limit exceeded
14 Execution timed out 8042 ms 99648 KB Time limit exceeded
15 Execution timed out 8045 ms 111888 KB Time limit exceeded
16 Execution timed out 8045 ms 127084 KB Time limit exceeded
17 Execution timed out 8035 ms 110228 KB Time limit exceeded