oj.uz

Submission #641305

# Submission time Handle Problem Language Result Execution time Memory
641305 2022-09-16T11:04:49 Z Cookie Regions (IOI09_regions) C++14
70 / 100
 8000 ms 29696 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 7 ms 11472 KB Output is correct
2 Correct 6 ms 11392 KB Output is correct
3 Correct 8 ms 11472 KB Output is correct
4 Correct 9 ms 11472 KB Output is correct
5 Correct 11 ms 11472 KB Output is correct
6 Correct 25 ms 11472 KB Output is correct
7 Correct 28 ms 11472 KB Output is correct
8 Correct 35 ms 11600 KB Output is correct
9 Correct 48 ms 11984 KB Output is correct
10 Correct 81 ms 12032 KB Output is correct
11 Correct 139 ms 12304 KB Output is correct
12 Correct 141 ms 12752 KB Output is correct
13 Correct 199 ms 12624 KB Output is correct
14 Correct 273 ms 13236 KB Output is correct
15 Correct 293 ms 15172 KB Output is correct

Subtask #2
55.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8071 ms 16104 KB Time limit exceeded
2 Execution timed out 8058 ms 15124 KB Time limit exceeded
3 Execution timed out 8096 ms 17736 KB Time limit exceeded
4 Correct 269 ms 13272 KB Output is correct
5 Correct 384 ms 14452 KB Output is correct
6 Correct 1536 ms 14416 KB Output is correct
7 Correct 1747 ms 15640 KB Output is correct
8 Correct 1283 ms 19648 KB Output is correct
9 Correct 2475 ms 21244 KB Output is correct
10 Correct 4658 ms 25036 KB Output is correct
11 Correct 4579 ms 21520 KB Output is correct
12 Correct 5501 ms 22836 KB Output is correct
13 Correct 6169 ms 22796 KB Output is correct
14 Execution timed out 8048 ms 22812 KB Time limit exceeded
15 Execution timed out 8021 ms 26208 KB Time limit exceeded
16 Correct 7228 ms 29696 KB Output is correct
17 Execution timed out 8034 ms 28852 KB Time limit exceeded