oj.uz

Submission #899731

# Submission time Handle Problem Language Result Execution time Memory
899731 2024-01-06T23:03:44 Z boyliguanhan Regions (IOI09_regions) C++17
0 / 100
 62 ms 14908 KB 
#include<bits/stdc++.h>
#include<bits/extc++.h>
#define N 200100
#define M 25010
using namespace __gnu_pbds;
#pragma GCC optimize(2)
#define l int
int read(){
    char x = getchar();
    int val = 0;
    while(x<'0'||x>'9')x=getchar();
    while('0'<=x&&x<='9')
        val = val*10+x-'0', x=getchar();
    return val;
}
void print(int num){
    if(num<0){
        putchar('-');
        num*=-1;
    }
    if(num>9) {
        print(num/10);
    }
    putchar((num%10)^48);
}
using namespace std;
vector<l> adj[M], peop[M];
vector<pair<l,l>> arr[M];
l region[M], t, in[M], out[M], li[M], sz[M], lg[450], ans1[450][M], ans2[M][450];
void dfs(l n){
    in[n]=t++;
    arr[region[n]].push_back({in[n],1});
    for(auto i: adj[n])
        dfs(i);
    out[n]=t++;
    arr[region[n]].push_back({out[n],0});
}
int query(int a, int b) {
    int i = 0, j = 0, res = 0;
    int an = arr[a].size(), bn = sz[b];
    while (i < an && j < bn)
        if (arr[a][i].first < in[peop[b][j]])
            i++;
        else
            res += arr[a][i].second,j++;
    return res;
}
int main(){
    l n=read(), r=read(), q=read(), lr=0;
    region[1]=read();
    sz[region[1]]++;
    peop[region[1]].push_back(1);
    for(l i = 2; i <= n; i++){
        adj[read()].push_back(i);
        region[i] = read();
        sz[region[i]]++;
        peop[region[i]].push_back(i);
    }
    for(int i = 1; i <= r; i++)
        if(sz[i]>449) {
            li[i]=++lr;
            for(int j = 1; j <= r; j++)
                ans1[i][j]=query(i,j),ans2[j][i]=query(j,i);
        }
    dfs(1);
    while(q--){
        int r1=read(), r2=read();
        if(li[r1])
            print(ans1[li[r1]][r2]);
        else if(li[r2])
            print(ans2[r1][li[r2]]);
        else
            print(query(r1, r2));
        puts("");
        fflush(stdout);
    }
    return 0;
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4184 KB Output isn't correct
2 Incorrect 1 ms 4184 KB Output isn't correct
3 Incorrect 2 ms 4184 KB Output isn't correct
4 Incorrect 3 ms 4184 KB Output isn't correct
5 Incorrect 4 ms 4184 KB Output isn't correct
6 Incorrect 7 ms 4184 KB Output isn't correct
7 Incorrect 12 ms 4184 KB Output isn't correct
8 Incorrect 15 ms 4184 KB Output isn't correct
9 Incorrect 24 ms 4696 KB Output isn't correct
10 Incorrect 37 ms 4692 KB Output isn't correct
11 Incorrect 52 ms 5460 KB Output isn't correct
12 Incorrect 62 ms 5976 KB Output isn't correct
13 Incorrect 57 ms 5460 KB Output isn't correct
14 Runtime error 9 ms 10112 KB Execution killed with signal 11
15 Runtime error 8 ms 10328 KB Execution killed with signal 11

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 10328 KB Execution killed with signal 11
2 Runtime error 8 ms 9600 KB Execution killed with signal 11
3 Runtime error 14 ms 14424 KB Execution killed with signal 11
4 Runtime error 10 ms 10328 KB Execution killed with signal 6
5 Runtime error 9 ms 10264 KB Execution killed with signal 11
6 Runtime error 11 ms 10072 KB Execution killed with signal 11
7 Runtime error 17 ms 14452 KB Execution killed with signal 11
8 Runtime error 9 ms 10328 KB Execution killed with signal 11
9 Runtime error 15 ms 14660 KB Execution killed with signal 11
10 Runtime error 10 ms 10568 KB Execution killed with signal 11
11 Runtime error 16 ms 14084 KB Execution killed with signal 11
12 Runtime error 10 ms 10764 KB Execution killed with signal 11
13 Runtime error 9 ms 10328 KB Execution killed with signal 11
14 Runtime error 10 ms 10140 KB Execution killed with signal 11
15 Runtime error 16 ms 14908 KB Execution killed with signal 11
16 Runtime error 11 ms 10584 KB Execution killed with signal 11
17 Runtime error 10 ms 10608 KB Execution killed with signal 11