oj.uz

Submission #641304

# Submission time Handle Problem Language Result Execution time Memory
641304 2022-09-16T11:04:01 Z Cookie Regions (IOI09_regions) C++14
35 / 100
 4199 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;
       
        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 11472 KB Output is correct
4 Correct 7 ms 11472 KB Output is correct
5 Correct 13 ms 11472 KB Output is correct
6 Correct 20 ms 11472 KB Output is correct
7 Correct 33 ms 11472 KB Output is correct
8 Correct 39 ms 11536 KB Output is correct
9 Correct 55 ms 11984 KB Output is correct
10 Correct 75 ms 12112 KB Output is correct
11 Correct 94 ms 12368 KB Output is correct
12 Correct 155 ms 12752 KB Output is correct
13 Correct 185 ms 12624 KB Output is correct
14 Correct 288 ms 13220 KB Output is correct
15 Correct 264 ms 15180 KB Output is correct

Subtask #2
20.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 80 ms 131072 KB Execution killed with signal 9
2 Runtime error 89 ms 131072 KB Execution killed with signal 9
3 Runtime error 79 ms 131072 KB Execution killed with signal 9
4 Correct 271 ms 13280 KB Output is correct
5 Correct 353 ms 14416 KB Output is correct
6 Runtime error 72 ms 131072 KB Execution killed with signal 9
7 Runtime error 87 ms 131072 KB Execution killed with signal 9
8 Runtime error 77 ms 131072 KB Execution killed with signal 9
9 Correct 1941 ms 21240 KB Output is correct
10 Runtime error 109 ms 131072 KB Execution killed with signal 9
11 Correct 4199 ms 21520 KB Output is correct
12 Runtime error 102 ms 131072 KB Execution killed with signal 9
13 Runtime error 101 ms 131072 KB Execution killed with signal 9
14 Runtime error 122 ms 131072 KB Execution killed with signal 9
15 Runtime error 111 ms 131072 KB Execution killed with signal 9
16 Runtime error 103 ms 131072 KB Execution killed with signal 9
17 Runtime error 102 ms 131072 KB Execution killed with signal 9