oj.uz

Submission #979439

# Submission time Handle Problem Language Result Execution time Memory
979439 2024-05-11T00:47:03 Z AlphaMale06 Regions (IOI09_regions) C++17
0 / 100
 3982 ms 65880 KB 
#include <bits/stdc++.h>

using namespace std;

#define F first
#define S second

const int N = 2e5+3;
const int inf = 1e9;
vector<int> g[N];
set<pair<int, int>> answered;
map<pair<int, int>, int> answer;
int a[N], tin[N], tout[N], cnt[N];
vector<pair<int, int>> posin[N], posout[N];
vector<int> pos[N];
int timer=1;

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

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);
    for(int i=1; i<=n; i++){
        pos[a[i]].push_back(i);
        posin[a[i]].push_back({tin[i], posin[a[i]].size()+1});
        posout[a[i]].push_back({tout[i], posout[a[i]].size()+1});
    }
    for(int i=1; i<=r; i++){
        posin[i].push_back({2*N, cnt[i]+1});
        posout[i].push_back({2*N, cnt[i]+1});
        posin[i].push_back({0, 0});
        posout[i].push_back({0, 0});
        sort(posin[i].begin(), posin[i].end());
        sort(posout[i].begin(), posout[i].end());
    }
    for(int i=1; i<=r; i++){
        for(int j=0; j<posin[i].size(); j++){
            posin[i][j].S=j;
            posout[i][j].S=j;
        }
    }
    for(int i=0; i<q; i++){
        int u, v;
        cin >> u >> v;
        if(answered.find({u, v})!=answered.end()){
            cout << answer[{u, v}] << endl;
            continue;
        }
        int ans=0;
        if(cnt[u]>cnt[v]){ //gledas za svakog v na gore
            int col = a[u];
            for(int e : pos[v]){
                auto ptr = upper_bound(posin[col].begin(), posin[col].end(), make_pair(tin[e], inf));
                ans += (*ptr).S; //dodas sve kojima je tin manji
                ptr = upper_bound(posout[col].begin(), posout[col].end(), make_pair(tin[e], inf));
                ans -= (*ptr).S; //oduzmes sve kojima je i tout manji
            }
        }
        else{//gledas za svako u na dole
            int col = a[v];
            for(int e : pos[u]){
                auto ptr = upper_bound(posin[col].begin(), posin[col].end(), make_pair(tout[e], inf));
                ans += (*ptr).S;
                ptr = lower_bound(posin[col].begin(), posin[col].end(), make_pair(tin[e], -1));
                ans -= (*ptr).S;
            }
        }
        answered.insert({u, v});
        answer[{u, v}] = ans;
        cout << ans << endl;
    }
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:53:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |         for(int j=0; j<posin[i].size(); j++){
      |                      ~^~~~~~~~~~~~~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 22360 KB Output isn't correct
2 Incorrect 5 ms 22360 KB Output isn't correct
3 Incorrect 7 ms 22632 KB Output isn't correct
4 Incorrect 7 ms 22388 KB Output isn't correct
5 Incorrect 9 ms 22940 KB Output isn't correct
6 Incorrect 14 ms 23016 KB Output isn't correct
7 Incorrect 21 ms 23508 KB Output isn't correct
8 Incorrect 25 ms 23488 KB Output isn't correct
9 Incorrect 35 ms 24048 KB Output isn't correct
10 Incorrect 58 ms 24544 KB Output isn't correct
11 Incorrect 98 ms 25016 KB Output isn't correct
12 Incorrect 100 ms 25680 KB Output isn't correct
13 Incorrect 163 ms 25244 KB Output isn't correct
14 Incorrect 233 ms 26832 KB Output isn't correct
15 Incorrect 200 ms 29332 KB Output isn't correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1032 ms 31320 KB Output isn't correct
2 Incorrect 1208 ms 29936 KB Output isn't correct
3 Incorrect 2003 ms 36808 KB Output isn't correct
4 Incorrect 171 ms 27584 KB Output isn't correct
5 Incorrect 257 ms 30440 KB Output isn't correct
6 Incorrect 417 ms 30124 KB Output isn't correct
7 Incorrect 560 ms 30592 KB Output isn't correct
8 Incorrect 727 ms 40524 KB Output isn't correct
9 Incorrect 1677 ms 48472 KB Output isn't correct
10 Incorrect 3089 ms 57988 KB Output isn't correct
11 Incorrect 3982 ms 55872 KB Output isn't correct
12 Incorrect 1292 ms 44668 KB Output isn't correct
13 Incorrect 1910 ms 48036 KB Output isn't correct
14 Incorrect 2122 ms 51252 KB Output isn't correct
15 Incorrect 3015 ms 60344 KB Output isn't correct
16 Incorrect 2580 ms 65880 KB Output isn't correct
17 Incorrect 2626 ms 64184 KB Output isn't correct