oj.uz

Submission #794584

# Submission time Handle Problem Language Result Execution time Memory
794584 2023-07-26T15:54:10 Z Cookie Regions (IOI09_regions) C++14
0 / 100
 197 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] << "\n";
        }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 << "\n";
        }
    }
    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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 22 ms 47312 KB Time limit exceeded (wall clock)
2 Execution timed out 21 ms 47192 KB Time limit exceeded (wall clock)
3 Execution timed out 21 ms 47360 KB Time limit exceeded (wall clock)
4 Execution timed out 25 ms 47252 KB Time limit exceeded (wall clock)
5 Execution timed out 25 ms 47312 KB Time limit exceeded (wall clock)
6 Execution timed out 20 ms 47312 KB Time limit exceeded (wall clock)
7 Execution timed out 21 ms 47312 KB Time limit exceeded (wall clock)
8 Execution timed out 20 ms 47312 KB Time limit exceeded (wall clock)
9 Execution timed out 23 ms 47740 KB Time limit exceeded (wall clock)
10 Execution timed out 23 ms 47816 KB Time limit exceeded (wall clock)
11 Execution timed out 23 ms 48080 KB Time limit exceeded (wall clock)
12 Execution timed out 25 ms 48500 KB Time limit exceeded (wall clock)
13 Execution timed out 27 ms 48208 KB Time limit exceeded (wall clock)
14 Execution timed out 28 ms 48820 KB Time limit exceeded (wall clock)
15 Execution timed out 27 ms 51408 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 98 ms 108924 KB Execution killed with signal 11
2 Runtime error 97 ms 106780 KB Execution killed with signal 11
3 Runtime error 106 ms 113168 KB Execution killed with signal 11
4 Execution timed out 31 ms 48920 KB Time limit exceeded (wall clock)
5 Execution timed out 33 ms 50548 KB Time limit exceeded (wall clock)
6 Execution timed out 40 ms 50112 KB Time limit exceeded (wall clock)
7 Execution timed out 37 ms 51144 KB Time limit exceeded (wall clock)
8 Execution timed out 43 ms 56280 KB Time limit exceeded (wall clock)
9 Execution timed out 60 ms 56700 KB Time limit exceeded (wall clock)
10 Execution timed out 68 ms 61728 KB Time limit exceeded (wall clock)
11 Execution timed out 93 ms 56508 KB Time limit exceeded (wall clock)
12 Runtime error 194 ms 126908 KB Execution killed with signal 11
13 Runtime error 182 ms 127276 KB Execution killed with signal 11
14 Runtime error 177 ms 127872 KB Execution killed with signal 11
15 Runtime error 171 ms 131072 KB Execution killed with signal 11
16 Runtime error 190 ms 131072 KB Execution killed with signal 11
17 Runtime error 197 ms 131072 KB Execution killed with signal 11