oj.uz

Submission #794570

# Submission time Handle Problem Language Result Execution time Memory
794570 2023-07-26T15:48:37 Z Cookie Regions (IOI09_regions) C++14
0 / 100
 150 ms 90120 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 << "\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 9 ms 19112 KB Time limit exceeded (wall clock)
2 Execution timed out 7 ms 19024 KB Time limit exceeded (wall clock)
3 Execution timed out 8 ms 19024 KB Time limit exceeded (wall clock)
4 Execution timed out 7 ms 19024 KB Time limit exceeded (wall clock)
5 Execution timed out 7 ms 19164 KB Time limit exceeded (wall clock)
6 Execution timed out 9 ms 19108 KB Time limit exceeded (wall clock)
7 Execution timed out 9 ms 19172 KB Time limit exceeded (wall clock)
8 Execution timed out 12 ms 19152 KB Time limit exceeded (wall clock)
9 Execution timed out 11 ms 19548 KB Time limit exceeded (wall clock)
10 Execution timed out 11 ms 19536 KB Time limit exceeded (wall clock)
11 Execution timed out 12 ms 19920 KB Time limit exceeded (wall clock)
12 Execution timed out 16 ms 20432 KB Time limit exceeded (wall clock)
13 Execution timed out 15 ms 20048 KB Time limit exceeded (wall clock)
14 Execution timed out 17 ms 20620 KB Time limit exceeded (wall clock)
15 Execution timed out 17 ms 23132 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 62 ms 51744 KB Execution killed with signal 11
2 Runtime error 66 ms 49548 KB Execution killed with signal 11
3 Runtime error 69 ms 56084 KB Execution killed with signal 11
4 Execution timed out 16 ms 20764 KB Time limit exceeded (wall clock)
5 Execution timed out 21 ms 22352 KB Time limit exceeded (wall clock)
6 Runtime error 51 ms 47284 KB Execution killed with signal 11
7 Runtime error 71 ms 50312 KB Execution killed with signal 11
8 Runtime error 80 ms 61904 KB Execution killed with signal 11
9 Execution timed out 48 ms 28440 KB Time limit exceeded (wall clock)
10 Runtime error 124 ms 76600 KB Execution killed with signal 11
11 Execution timed out 63 ms 28328 KB Time limit exceeded (wall clock)
12 Runtime error 137 ms 69756 KB Execution killed with signal 11
13 Runtime error 148 ms 70196 KB Execution killed with signal 11
14 Runtime error 137 ms 70632 KB Execution killed with signal 11
15 Runtime error 139 ms 79612 KB Execution killed with signal 11
16 Runtime error 139 ms 90120 KB Execution killed with signal 11
17 Runtime error 150 ms 87680 KB Execution killed with signal 11