oj.uz

Submission #641308

# Submission time Handle Problem Language Result Execution time Memory
641308 2022-09-16T11:10:21 Z Cookie Regions (IOI09_regions) C++14
100 / 100
 4840 ms 97528 KB 
#include<bits/stdc++.h>
 
using namespace std;
#include<fstream>
 
#define ll long long
#define vt vector
#define pb push_back
#define fi first
#define se second
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
typedef unsigned long long ull;
 
#define pii pair<int, int>
 
#define pll pair<ll, ll>
#include<fstream>
 
ifstream fin("milkorder.in");
ofstream fout("milkorder.out");
 
const ll mod = 1e9 + 7;
const int mxn = 2e5, mxr = 25e3, sq = 446;
int n, r, q, t = 0;
vt<int>adj[mxn + 1], ob[mxn + 1];
vt<int>reg[mxr + 3];
int in[mxn + 1], out[mxn + 1], color[mxn + 1], h[mxn + 1];
map<int, int>mp[mxr + 1];
void dfs(int s){
    in[s] = ++t;
    color[t] = h[s];
    for(auto i: adj[s]){
        
        dfs(i);
        
    }
    out[s] = t;
}
void dfs2(int co, int s, int cnt){
    for(auto i: adj[s]){
        mp[co][h[i]] += cnt;
        dfs2(co, i, cnt + (h[i] == co));
    }
}
int main(){
     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> r >> q;
    cin >> h[1]; reg[h[1]].pb(1);
    forr(i, 2, n + 1){
        int v; cin >> v >> h[i];
        reg[h[i]].pb(i);
        adj[v].pb(i);
    }
    for(int i = 1; i <= r; i++){
        if(reg[i].size() >= sq){
            dfs2(i, 1, (h[1] == i));
        }
        
    }
    dfs(1);
    forr(i, 1, n + 1)ob[color[i]].pb(i);
    for(int i = 0; i < q; i++){
    
        int r1, r2; cin >> r1 >> r2;
        if(reg[r1].size() >= sq){
            cout << mp[r1][r2] << endl;
        }else{
        int ans = 0;
        for(auto j: reg[r1]){
            ans += upper_bound(ob[r2].begin(), ob[r2].end(), out[j]) - lower_bound(ob[r2].begin(), ob[r2].end(), in[j]);
            
        }
        cout << ans << endl;
        }
    }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11472 KB Output is correct
2 Correct 6 ms 11472 KB Output is correct
3 Correct 7 ms 11472 KB Output is correct
4 Correct 10 ms 11504 KB Output is correct
5 Correct 14 ms 11528 KB Output is correct
6 Correct 34 ms 11472 KB Output is correct
7 Correct 34 ms 11568 KB Output is correct
8 Correct 36 ms 11600 KB Output is correct
9 Correct 50 ms 11984 KB Output is correct
10 Correct 72 ms 11984 KB Output is correct
11 Correct 144 ms 12368 KB Output is correct
12 Correct 161 ms 12932 KB Output is correct
13 Correct 184 ms 12536 KB Output is correct
14 Correct 302 ms 13220 KB Output is correct
15 Correct 278 ms 15084 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1851 ms 17520 KB Output is correct
2 Correct 1971 ms 15540 KB Output is correct
3 Correct 2715 ms 20644 KB Output is correct
4 Correct 262 ms 13276 KB Output is correct
5 Correct 293 ms 14416 KB Output is correct
6 Correct 927 ms 32268 KB Output is correct
7 Correct 1745 ms 24416 KB Output is correct
8 Correct 2155 ms 71948 KB Output is correct
9 Correct 2152 ms 21240 KB Output is correct
10 Correct 4840 ms 97528 KB Output is correct
11 Correct 4510 ms 21524 KB Output is correct
12 Correct 1515 ms 24460 KB Output is correct
13 Correct 1812 ms 25616 KB Output is correct
14 Correct 2965 ms 41100 KB Output is correct
15 Correct 2956 ms 34056 KB Output is correct
16 Correct 2992 ms 46896 KB Output is correct
17 Correct 3225 ms 60536 KB Output is correct