oj.uz

Submission #979435

# Submission time Handle Problem Language Result Execution time Memory
979435 2024-05-11T00:32:45 Z AlphaMale06 Regions (IOI09_regions) C++17
0 / 100
 4704 ms 66296 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(tout[e], inf));
                ans += (*ptr).S; //dodas sve kojima je tin manji
                ptr = upper_bound(posout[col].begin(), posout[col].end(), make_pair(tout[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 7 ms 22360 KB Output isn't correct
2 Incorrect 5 ms 22360 KB Output isn't correct
3 Incorrect 6 ms 22368 KB Output isn't correct
4 Incorrect 7 ms 22896 KB Output isn't correct
5 Incorrect 9 ms 22676 KB Output isn't correct
6 Incorrect 13 ms 23032 KB Output isn't correct
7 Incorrect 19 ms 23276 KB Output isn't correct
8 Incorrect 27 ms 23304 KB Output isn't correct
9 Incorrect 35 ms 24112 KB Output isn't correct
10 Incorrect 63 ms 25172 KB Output isn't correct
11 Incorrect 96 ms 24848 KB Output isn't correct
12 Incorrect 101 ms 25644 KB Output isn't correct
13 Incorrect 150 ms 26160 KB Output isn't correct
14 Incorrect 250 ms 26044 KB Output isn't correct
15 Incorrect 216 ms 29220 KB Output isn't correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1064 ms 31336 KB Output isn't correct
2 Incorrect 1193 ms 30596 KB Output isn't correct
3 Incorrect 2001 ms 36856 KB Output isn't correct
4 Incorrect 189 ms 28144 KB Output isn't correct
5 Incorrect 249 ms 30380 KB Output isn't correct
6 Incorrect 415 ms 30156 KB Output isn't correct
7 Incorrect 579 ms 30692 KB Output isn't correct
8 Incorrect 766 ms 39756 KB Output isn't correct
9 Incorrect 1703 ms 48756 KB Output isn't correct
10 Incorrect 3660 ms 57688 KB Output isn't correct
11 Incorrect 4704 ms 55144 KB Output isn't correct
12 Incorrect 1462 ms 43916 KB Output isn't correct
13 Incorrect 2052 ms 47636 KB Output isn't correct
14 Incorrect 2178 ms 50628 KB Output isn't correct
15 Incorrect 3067 ms 59564 KB Output isn't correct
16 Incorrect 2557 ms 66296 KB Output isn't correct
17 Incorrect 2600 ms 64432 KB Output isn't correct