oj.uz

Submission #641302

# Submission time Handle Problem Language Result Execution time Memory
641302 2022-09-16T10:51:54 Z Cookie Regions (IOI09_regions) C++14
75 / 100
 8000 ms 31492 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];
void dfs(int s, int pre){
    in[s] = ++t;
    color[t] = h[s];
    for(auto i: adj[s]){
        if(i != pre){
            dfs(i, s);
        }
    }
    out[s] = t;
}
void solve(int r1, int r2){
    
}
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);
    }
    dfs(1, -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 5 ms 10320 KB Output is correct
2 Correct 6 ms 10320 KB Output is correct
3 Correct 6 ms 10320 KB Output is correct
4 Correct 7 ms 10320 KB Output is correct
5 Correct 12 ms 10320 KB Output is correct
6 Correct 20 ms 10320 KB Output is correct
7 Correct 33 ms 10320 KB Output is correct
8 Correct 28 ms 10448 KB Output is correct
9 Correct 55 ms 10832 KB Output is correct
10 Correct 90 ms 10832 KB Output is correct
11 Correct 125 ms 11168 KB Output is correct
12 Correct 122 ms 11696 KB Output is correct
13 Correct 213 ms 11344 KB Output is correct
14 Correct 313 ms 12044 KB Output is correct
15 Correct 316 ms 14628 KB Output is correct

Subtask #2
60.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8039 ms 15224 KB Time limit exceeded
2 Execution timed out 8058 ms 13992 KB Time limit exceeded
3 Execution timed out 8086 ms 17028 KB Time limit exceeded
4 Correct 210 ms 12240 KB Output is correct
5 Correct 245 ms 13720 KB Output is correct
6 Correct 1524 ms 13384 KB Output is correct
7 Correct 1669 ms 14440 KB Output is correct
8 Correct 1111 ms 19572 KB Output is correct
9 Correct 2044 ms 20360 KB Output is correct
10 Correct 4280 ms 25292 KB Output is correct
11 Correct 4267 ms 20476 KB Output is correct
12 Correct 4985 ms 21712 KB Output is correct
13 Correct 5571 ms 21920 KB Output is correct
14 Correct 7711 ms 21816 KB Output is correct
15 Execution timed out 8038 ms 26184 KB Time limit exceeded
16 Correct 5590 ms 31492 KB Output is correct
17 Execution timed out 8028 ms 30280 KB Time limit exceeded