oj.uz

Submission #641306

# Submission time Handle Problem Language Result Execution time Memory
641306 2022-09-16T11:05:17 Z Cookie Regions (IOI09_regions) C++14
70 / 100
 8000 ms 29700 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;
       
        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 11400 KB Output is correct
4 Correct 9 ms 11484 KB Output is correct
5 Correct 12 ms 11472 KB Output is correct
6 Correct 19 ms 11472 KB Output is correct
7 Correct 29 ms 11472 KB Output is correct
8 Correct 36 ms 11600 KB Output is correct
9 Correct 45 ms 11856 KB Output is correct
10 Correct 76 ms 11984 KB Output is correct
11 Correct 131 ms 12320 KB Output is correct
12 Correct 162 ms 12752 KB Output is correct
13 Correct 184 ms 12620 KB Output is correct
14 Correct 335 ms 13220 KB Output is correct
15 Correct 222 ms 15188 KB Output is correct

Subtask #2
55.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8023 ms 16116 KB Time limit exceeded
2 Execution timed out 8071 ms 15184 KB Time limit exceeded
3 Execution timed out 8038 ms 17764 KB Time limit exceeded
4 Correct 300 ms 13268 KB Output is correct
5 Correct 390 ms 14440 KB Output is correct
6 Correct 1432 ms 14416 KB Output is correct
7 Correct 1885 ms 15572 KB Output is correct
8 Correct 1335 ms 19660 KB Output is correct
9 Correct 2734 ms 21244 KB Output is correct
10 Correct 4613 ms 25160 KB Output is correct
11 Correct 4689 ms 21520 KB Output is correct
12 Correct 5871 ms 22844 KB Output is correct
13 Correct 5923 ms 22796 KB Output is correct
14 Execution timed out 8009 ms 22856 KB Time limit exceeded
15 Execution timed out 8010 ms 26284 KB Time limit exceeded
16 Correct 6555 ms 29700 KB Output is correct
17 Execution timed out 8055 ms 28744 KB Time limit exceeded