oj.uz

Submission #236315

# Submission time Handle Problem Language Result Execution time Memory
236315 2020-06-01T10:17:21 Z nicolaalexandra Regions (IOI09_regions) C++14
70 / 100
 8000 ms 29436 KB 
#include <bits/stdc++.h>
#define DIM 200010
#define INF 2000000000
using namespace std;

vector <int> L[DIM],v[DIM];
int E[DIM],c[DIM];
pair <int,int> poz[DIM];
int n,r,q,i,x,r1,r2,k;

void dfs (int nod, int tata){
    E[++k] = nod;
    poz[nod].first = k;
    for (auto vecin : L[nod]){
        if (vecin != tata)
            dfs (vecin,nod);
    }
    poz[nod].second = k;
}
int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>n>>r>>q;
    cin>>c[1];
    for (i=2;i<=n;i++){
        cin>>x>>c[i];
        L[x].push_back(i);
        L[i].push_back(x);
    }

    dfs (1,0);

    for (i=1;i<=k;i++){
        int nod = E[i];
        v[c[nod]].push_back(nod);
    }

    /// vreau sa vad cat de prost merge asta

    for (;q--;){
        cin>>r1>>r2;
        int sol = 0;
        for (auto it : v[r1]){

            /// cate noduri de cu regiunea r2 sunt in subarborele asta
            int x = poz[it].first, y = poz[it].second;

            int st = 0, dr = v[r2].size()-1, sol_st = INF;
            while (st <= dr){
                int mid = (st+dr)>>1;
                if (poz[v[r2][mid]].first >= x){
                    sol_st = mid;
                    dr = mid-1;
                } else st = mid+1;
            }

            st = 0, dr = v[r2].size()-1; int sol_dr = -1;
            while (st <= dr){
                int mid = (st+dr)>>1;
                if (poz[v[r2][mid]].first <= y){
                    sol_dr = mid;
                    st = mid+1;
                } else dr = mid-1;
            }

            if (sol_st <= sol_dr)
                sol += sol_dr - sol_st + 1;

        }
        cout<<sol<<endl;
    }

    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 9728 KB Output is correct
2 Correct 10 ms 9728 KB Output is correct
3 Correct 11 ms 9728 KB Output is correct
4 Correct 13 ms 9728 KB Output is correct
5 Correct 17 ms 9728 KB Output is correct
6 Correct 28 ms 9728 KB Output is correct
7 Correct 37 ms 9856 KB Output is correct
8 Correct 44 ms 9856 KB Output is correct
9 Correct 54 ms 10240 KB Output is correct
10 Correct 94 ms 10240 KB Output is correct
11 Correct 159 ms 10624 KB Output is correct
12 Correct 163 ms 11008 KB Output is correct
13 Correct 230 ms 11008 KB Output is correct
14 Correct 286 ms 11360 KB Output is correct
15 Correct 305 ms 13688 KB Output is correct

Subtask #2
55.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8016 ms 14328 KB Time limit exceeded
2 Execution timed out 8044 ms 14104 KB Time limit exceeded
3 Execution timed out 8061 ms 15992 KB Time limit exceeded
4 Correct 291 ms 11512 KB Output is correct
5 Correct 455 ms 12920 KB Output is correct
6 Correct 1623 ms 12792 KB Output is correct
7 Correct 1918 ms 13816 KB Output is correct
8 Correct 1468 ms 18296 KB Output is correct
9 Correct 2493 ms 19064 KB Output is correct
10 Correct 4736 ms 23288 KB Output is correct
11 Correct 4556 ms 21176 KB Output is correct
12 Correct 4770 ms 19964 KB Output is correct
13 Correct 5421 ms 20976 KB Output is correct
14 Correct 7228 ms 21112 KB Output is correct
15 Execution timed out 8010 ms 24056 KB Time limit exceeded
16 Execution timed out 8003 ms 29436 KB Time limit exceeded
17 Execution timed out 8045 ms 28280 KB Time limit exceeded