oj.uz

Submission #978918

# Submission time Handle Problem Language Result Execution time Memory
978918 2024-05-10T02:50:20 Z AlphaMale06 Regions (IOI09_regions) C++17
0 / 100
 53 ms 24704 KB 
#include <bits/stdc++.h>

using namespace std;

struct query{
    int a, b, ind, ans;
};

const int N = 2e5+3;

vector<int> g[N];
int a[N], tin[N], tout[N], cnt[N];
int f[2*N];
int timer=1;

void dfs(int v, int p){
    tin[v]=timer++;
    for(int to : g[v])dfs(to, v);
    tout[v]=timer++;
}

bool cmp(query A, query B){
    return A.a < B.a;
}

bool cmp2(query A, query B){
    return A.ind<B.ind;
}

void Update(int ind, int val){
    for(int i=ind; i<2*N; i+=i&-i)f[i]+=val;
}

int Get(int ind){
    int ret=0;
    for(int i=ind; i>0; i-=i&-i)ret+=f[i];
    return ret;
}

int Get(int l, int r){
    return Get(r)-Get(l-1);
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, r, q;
    cin >> n >> r >> q;
    cin >> a[1];
    cnt[a[1]]++;
    for(int i=2; i<=n; i++){
        int x;
        cin >> x >> a[i];
        cnt[a[i]]++;
        g[x].push_back(i);
    }
    dfs(1, 1);
    vector<query> ups;
    vector<query> downs;
    for(int i=0; i<q; i++){
        int u, v;
        cin >> u >> v;
        if(cnt[u]>cnt[v])ups.push_back({u, v, i, 0});
        else downs.push_back({v, u, i, 0});
    }
    sort(downs.begin(), downs.end(), cmp);
    sort(ups.begin(), ups.end(), cmp);
    vector<int> pos[r+1];
    for(int i=1; i<=n; i++){
        pos[a[i]].push_back(i);
    }
    if(downs.size()){
        for(int e : pos[downs[0].a])Update(tin[e], 1);
        for(int e : pos[downs[0].b])downs[0].ans+=Get(tin[e], tout[e]);
        for(int i=1; i<downs.size(); i++){
            if(downs[i].a!=downs[i-1].a){
                for(int e : pos[downs[i-1].a])Update(tin[e], -1);
                for(int e : pos[downs[i].a])Update(tin[e], 1);
            }
            for(int e : pos[downs[i].b])downs[i].ans+=Get(tin[e], tout[e]);
        }
    }
    for(int i=0; i<2*N; i++)f[i]=0;
    if(ups.size()){
        for(int e : pos[ups[0].a]){
            Update(tin[e], 1);
            Update(tout[e], -1);
        }
        for(int e : pos[ups[0].b])ups[0].ans+=Get(0, tin[e]);
        for(int i=1; i<ups.size(); i++){
            if(ups[i].a!=ups[i-1].a){
                for(int e : pos[ups[i-1].a]){
                    Update(tin[e], -1);
                    Update(tout[e], 1);
                }
                for(int e : pos[ups[i].a]){
                    Update(tin[e], 1);
                    Update(tout[e], -1);
                }
            }
            for(int e : pos[ups[i].b])ups[i].ans+=Get(0, tin[e]);
        }
    }
    vector<query> svi;
    for(auto & e : downs)svi.push_back(e);
    for(auto & e : ups)svi.push_back(e);
    sort(svi.begin(), svi.end(), cmp2);
    for(auto & e : svi)cout << e.ans << '\n';
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:76:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |         for(int i=1; i<downs.size(); i++){
      |                      ~^~~~~~~~~~~~~
regions.cpp:91:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |         for(int i=1; i<ups.size(); i++){
      |                      ~^~~~~~~~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2 ms 9560 KB Time limit exceeded (wall clock)
2 Execution timed out 2 ms 9560 KB Time limit exceeded (wall clock)
3 Execution timed out 2 ms 9560 KB Time limit exceeded (wall clock)
4 Execution timed out 2 ms 9560 KB Time limit exceeded (wall clock)
5 Execution timed out 2 ms 9560 KB Time limit exceeded (wall clock)
6 Execution timed out 2 ms 9560 KB Time limit exceeded (wall clock)
7 Execution timed out 2 ms 9560 KB Time limit exceeded (wall clock)
8 Execution timed out 2 ms 9560 KB Time limit exceeded (wall clock)
9 Execution timed out 3 ms 9816 KB Time limit exceeded (wall clock)
10 Execution timed out 4 ms 9876 KB Time limit exceeded (wall clock)
11 Execution timed out 5 ms 9896 KB Time limit exceeded (wall clock)
12 Execution timed out 5 ms 10328 KB Time limit exceeded (wall clock)
13 Execution timed out 7 ms 10072 KB Time limit exceeded (wall clock)
14 Execution timed out 7 ms 10328 KB Time limit exceeded (wall clock)
15 Execution timed out 11 ms 12768 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 14 ms 12376 KB Time limit exceeded (wall clock)
2 Execution timed out 17 ms 11172 KB Time limit exceeded (wall clock)
3 Execution timed out 21 ms 13972 KB Time limit exceeded (wall clock)
4 Execution timed out 10 ms 10412 KB Time limit exceeded (wall clock)
5 Execution timed out 10 ms 11864 KB Time limit exceeded (wall clock)
6 Execution timed out 11 ms 11172 KB Time limit exceeded (wall clock)
7 Execution timed out 15 ms 11636 KB Time limit exceeded (wall clock)
8 Execution timed out 22 ms 15900 KB Time limit exceeded (wall clock)
9 Execution timed out 37 ms 14692 KB Time limit exceeded (wall clock)
10 Execution timed out 37 ms 19824 KB Time limit exceeded (wall clock)
11 Execution timed out 40 ms 13356 KB Time limit exceeded (wall clock)
12 Execution timed out 51 ms 15780 KB Time limit exceeded (wall clock)
13 Execution timed out 41 ms 15880 KB Time limit exceeded (wall clock)
14 Execution timed out 52 ms 15280 KB Time limit exceeded (wall clock)
15 Execution timed out 48 ms 19288 KB Time limit exceeded (wall clock)
16 Execution timed out 53 ms 24704 KB Time limit exceeded (wall clock)
17 Execution timed out 46 ms 23748 KB Time limit exceeded (wall clock)