oj.uz

Submission #794586

# Submission time Handle Problem Language Result Execution time Memory
794586 2023-07-26T15:55:21 Z Cookie Regions (IOI09_regions) C++14
55 / 100
 3759 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] << 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){
      |              ^
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 24 ms 47200 KB Output is correct
2 Correct 24 ms 47300 KB Output is correct
3 Correct 30 ms 47260 KB Output is correct
4 Correct 26 ms 47316 KB Output is correct
5 Correct 30 ms 47312 KB Output is correct
6 Correct 38 ms 47292 KB Output is correct
7 Correct 44 ms 47312 KB Output is correct
8 Correct 54 ms 47376 KB Output is correct
9 Correct 64 ms 47780 KB Output is correct
10 Correct 95 ms 47824 KB Output is correct
11 Correct 77 ms 48024 KB Output is correct
12 Correct 133 ms 48512 KB Output is correct
13 Correct 187 ms 48276 KB Output is correct
14 Correct 258 ms 48812 KB Output is correct
15 Correct 208 ms 51356 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 96 ms 108852 KB Execution killed with signal 11
2 Runtime error 96 ms 106760 KB Execution killed with signal 11
3 Runtime error 103 ms 113104 KB Execution killed with signal 11
4 Correct 246 ms 48984 KB Output is correct
5 Correct 334 ms 50512 KB Output is correct
6 Correct 1248 ms 50172 KB Output is correct
7 Correct 1436 ms 51188 KB Output is correct
8 Correct 1040 ms 56176 KB Output is correct
9 Correct 1978 ms 56668 KB Output is correct
10 Correct 3759 ms 61752 KB Output is correct
11 Correct 3507 ms 56548 KB Output is correct
12 Runtime error 165 ms 126936 KB Execution killed with signal 11
13 Runtime error 162 ms 127228 KB Execution killed with signal 11
14 Runtime error 186 ms 127856 KB Execution killed with signal 11
15 Runtime error 182 ms 131072 KB Execution killed with signal 11
16 Runtime error 172 ms 131072 KB Execution killed with signal 11
17 Runtime error 169 ms 131072 KB Execution killed with signal 11