oj.uz

Submission #794574

# Submission time Handle Problem Language Result Execution time Memory
794574 2023-07-26T15:50:30 Z Cookie Regions (IOI09_regions) C++14
0 / 100
 141 ms 90156 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 19024 KB Time limit exceeded (wall clock)
2 Execution timed out 9 ms 19024 KB Time limit exceeded (wall clock)
3 Execution timed out 9 ms 19024 KB Time limit exceeded (wall clock)
4 Execution timed out 11 ms 19024 KB Time limit exceeded (wall clock)
5 Execution timed out 9 ms 19084 KB Time limit exceeded (wall clock)
6 Execution timed out 10 ms 19152 KB Time limit exceeded (wall clock)
7 Execution timed out 9 ms 19152 KB Time limit exceeded (wall clock)
8 Execution timed out 9 ms 19152 KB Time limit exceeded (wall clock)
9 Execution timed out 10 ms 19556 KB Time limit exceeded (wall clock)
10 Execution timed out 11 ms 19536 KB Time limit exceeded (wall clock)
11 Execution timed out 14 ms 19920 KB Time limit exceeded (wall clock)
12 Execution timed out 13 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 20636 KB Time limit exceeded (wall clock)
15 Execution timed out 19 ms 23204 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 64 ms 51764 KB Execution killed with signal 11
2 Runtime error 61 ms 49624 KB Execution killed with signal 11
3 Runtime error 71 ms 56036 KB Execution killed with signal 11
4 Execution timed out 19 ms 20704 KB Time limit exceeded (wall clock)
5 Execution timed out 20 ms 22348 KB Time limit exceeded (wall clock)
6 Runtime error 56 ms 47332 KB Execution killed with signal 11
7 Runtime error 60 ms 50296 KB Execution killed with signal 11
8 Runtime error 83 ms 61976 KB Execution killed with signal 11
9 Execution timed out 48 ms 28432 KB Time limit exceeded (wall clock)
10 Runtime error 133 ms 76688 KB Execution killed with signal 11
11 Execution timed out 79 ms 28268 KB Time limit exceeded (wall clock)
12 Runtime error 130 ms 69724 KB Execution killed with signal 11
13 Runtime error 122 ms 70104 KB Execution killed with signal 11
14 Runtime error 137 ms 70632 KB Execution killed with signal 11
15 Runtime error 135 ms 79724 KB Execution killed with signal 11
16 Runtime error 137 ms 90156 KB Execution killed with signal 11
17 Runtime error 141 ms 87564 KB Execution killed with signal 11