oj.uz

Submission #641301

# Submission time Handle Problem Language Result Execution time Memory
641301 2022-09-16T10:50:48 Z Cookie Regions (IOI09_regions) C++14
13 / 100
 8000 ms 30424 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[mxr + 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
13.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10368 KB Output is correct
2 Correct 7 ms 10320 KB Output is correct
3 Correct 7 ms 10320 KB Output is correct
4 Correct 10 ms 10256 KB Output is correct
5 Correct 12 ms 10320 KB Output is correct
6 Correct 20 ms 10320 KB Output is correct
7 Correct 31 ms 10320 KB Output is correct
8 Correct 33 ms 10576 KB Output is correct
9 Correct 60 ms 10832 KB Output is correct
10 Correct 82 ms 10896 KB Output is correct
11 Correct 131 ms 11216 KB Output is correct
12 Correct 165 ms 11648 KB Output is correct
13 Correct 201 ms 11440 KB Output is correct
14 Incorrect 293 ms 12020 KB Output isn't correct
15 Incorrect 253 ms 14544 KB Output isn't correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8069 ms 15056 KB Time limit exceeded
2 Execution timed out 8077 ms 14024 KB Time limit exceeded
3 Execution timed out 8074 ms 16848 KB Time limit exceeded
4 Incorrect 188 ms 12112 KB Output isn't correct
5 Incorrect 257 ms 13632 KB Output isn't correct
6 Incorrect 1210 ms 13240 KB Output isn't correct
7 Incorrect 1465 ms 14404 KB Output isn't correct
8 Incorrect 1018 ms 19348 KB Output isn't correct
9 Incorrect 1952 ms 19592 KB Output isn't correct
10 Incorrect 3352 ms 24392 KB Output isn't correct
11 Incorrect 4097 ms 20292 KB Output isn't correct
12 Incorrect 4511 ms 21340 KB Output isn't correct
13 Incorrect 4502 ms 21560 KB Output isn't correct
14 Incorrect 7947 ms 21320 KB Output isn't correct
15 Incorrect 6330 ms 25300 KB Output isn't correct
16 Incorrect 4334 ms 30424 KB Output isn't correct
17 Incorrect 7953 ms 29384 KB Output isn't correct