oj.uz

Submission #641303

# Submission time Handle Problem Language Result Execution time Memory
641303 2022-09-16T11:00:54 Z Cookie Regions (IOI09_regions) C++14
35 / 100
 4639 ms 131072 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, s, 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 6 ms 11472 KB Output is correct
2 Correct 6 ms 11472 KB Output is correct
3 Correct 8 ms 11448 KB Output is correct
4 Correct 12 ms 11472 KB Output is correct
5 Correct 12 ms 11472 KB Output is correct
6 Correct 20 ms 11512 KB Output is correct
7 Correct 30 ms 11472 KB Output is correct
8 Correct 37 ms 11600 KB Output is correct
9 Correct 56 ms 11984 KB Output is correct
10 Correct 75 ms 11984 KB Output is correct
11 Correct 132 ms 12368 KB Output is correct
12 Correct 169 ms 12752 KB Output is correct
13 Correct 187 ms 12616 KB Output is correct
14 Correct 315 ms 13216 KB Output is correct
15 Correct 242 ms 15176 KB Output is correct

Subtask #2
20.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 76 ms 131072 KB Execution killed with signal 9
2 Runtime error 78 ms 131072 KB Execution killed with signal 9
3 Runtime error 75 ms 131072 KB Execution killed with signal 9
4 Correct 143 ms 13276 KB Output is correct
5 Correct 361 ms 14544 KB Output is correct
6 Runtime error 72 ms 131072 KB Execution killed with signal 9
7 Runtime error 74 ms 131072 KB Execution killed with signal 9
8 Runtime error 87 ms 131072 KB Execution killed with signal 9
9 Correct 2595 ms 21244 KB Output is correct
10 Runtime error 104 ms 131072 KB Execution killed with signal 9
11 Correct 4639 ms 21520 KB Output is correct
12 Runtime error 104 ms 131072 KB Execution killed with signal 9
13 Runtime error 104 ms 131072 KB Execution killed with signal 9
14 Runtime error 105 ms 131072 KB Execution killed with signal 9
15 Runtime error 137 ms 131072 KB Execution killed with signal 9
16 Runtime error 120 ms 131072 KB Execution killed with signal 9
17 Runtime error 113 ms 131072 KB Execution killed with signal 9