oj.uz

Submission #794581

# Submission time Handle Problem Language Result Execution time Memory
794581 2023-07-26T15:53:10 Z Cookie Regions (IOI09_regions) C++14
35 / 100
 3861 ms 90176 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 = 2e5 + 5, mxm = 1e5, sq = 400;
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 << 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 10 ms 19060 KB Output is correct
2 Correct 10 ms 19116 KB Output is correct
3 Correct 12 ms 19108 KB Output is correct
4 Correct 13 ms 19028 KB Output is correct
5 Correct 20 ms 19132 KB Output is correct
6 Correct 25 ms 19152 KB Output is correct
7 Correct 24 ms 19152 KB Output is correct
8 Correct 39 ms 19124 KB Output is correct
9 Correct 52 ms 19636 KB Output is correct
10 Correct 72 ms 19536 KB Output is correct
11 Correct 118 ms 19920 KB Output is correct
12 Correct 108 ms 20432 KB Output is correct
13 Correct 174 ms 20048 KB Output is correct
14 Correct 245 ms 20680 KB Output is correct
15 Correct 217 ms 23188 KB Output is correct

Subtask #2
20.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 61 ms 51740 KB Execution killed with signal 11
2 Runtime error 61 ms 49528 KB Execution killed with signal 11
3 Runtime error 75 ms 56044 KB Execution killed with signal 11
4 Correct 213 ms 20732 KB Output is correct
5 Correct 242 ms 22292 KB Output is correct
6 Runtime error 51 ms 47288 KB Execution killed with signal 11
7 Runtime error 68 ms 50352 KB Execution killed with signal 11
8 Runtime error 79 ms 61944 KB Execution killed with signal 11
9 Correct 1952 ms 28508 KB Output is correct
10 Runtime error 135 ms 76572 KB Execution killed with signal 11
11 Correct 3861 ms 28284 KB Output is correct
12 Runtime error 136 ms 69768 KB Execution killed with signal 11
13 Runtime error 128 ms 70076 KB Execution killed with signal 11
14 Runtime error 147 ms 70692 KB Execution killed with signal 11
15 Runtime error 152 ms 79696 KB Execution killed with signal 11
16 Runtime error 139 ms 90176 KB Execution killed with signal 11
17 Runtime error 153 ms 87668 KB Execution killed with signal 11