oj.uz

Submission #641307

# Submission time Handle Problem Language Result Execution time Memory
641307 2022-09-16T11:08:16 Z Cookie Regions (IOI09_regions) C++14
35 / 100
 4849 ms 97492 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] == cnt));
    }
}
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 7 ms 11472 KB Output is correct
2 Correct 6 ms 11472 KB Output is correct
3 Correct 8 ms 11472 KB Output is correct
4 Correct 10 ms 11472 KB Output is correct
5 Correct 13 ms 11472 KB Output is correct
6 Correct 17 ms 11472 KB Output is correct
7 Correct 27 ms 11540 KB Output is correct
8 Correct 32 ms 11600 KB Output is correct
9 Correct 52 ms 11984 KB Output is correct
10 Correct 73 ms 11984 KB Output is correct
11 Correct 106 ms 12368 KB Output is correct
12 Correct 138 ms 12752 KB Output is correct
13 Correct 167 ms 12748 KB Output is correct
14 Correct 306 ms 13216 KB Output is correct
15 Correct 265 ms 15164 KB Output is correct

Subtask #2
20.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1710 ms 17520 KB Output isn't correct
2 Incorrect 1868 ms 15544 KB Output isn't correct
3 Incorrect 2840 ms 20608 KB Output isn't correct
4 Correct 214 ms 13276 KB Output is correct
5 Correct 360 ms 14488 KB Output is correct
6 Incorrect 817 ms 32164 KB Output isn't correct
7 Incorrect 1740 ms 24444 KB Output isn't correct
8 Incorrect 1947 ms 72204 KB Output isn't correct
9 Correct 2206 ms 21248 KB Output is correct
10 Incorrect 4849 ms 97492 KB Output isn't correct
11 Correct 4498 ms 21524 KB Output is correct
12 Incorrect 1449 ms 24420 KB Output isn't correct
13 Incorrect 2031 ms 25608 KB Output isn't correct
14 Incorrect 2622 ms 41088 KB Output isn't correct
15 Incorrect 2780 ms 34064 KB Output isn't correct
16 Incorrect 2643 ms 46888 KB Output isn't correct
17 Incorrect 3107 ms 60528 KB Output isn't correct