oj.uz

Submission #979440

# Submission time Handle Problem Language Result Execution time Memory
979440 2024-05-11T00:51:20 Z AlphaMale06 Regions (IOI09_regions) C++17
0 / 100
 4078 ms 66484 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;
      	assert(u!=v);
        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 22628 KB Output isn't correct
4 Incorrect 8 ms 22900 KB Output isn't correct
5 Incorrect 9 ms 23184 KB Output isn't correct
6 Incorrect 15 ms 23024 KB Output isn't correct
7 Incorrect 24 ms 22912 KB Output isn't correct
8 Incorrect 26 ms 23616 KB Output isn't correct
9 Incorrect 34 ms 23816 KB Output isn't correct
10 Incorrect 59 ms 24808 KB Output isn't correct
11 Incorrect 107 ms 24672 KB Output isn't correct
12 Incorrect 111 ms 26172 KB Output isn't correct
13 Incorrect 153 ms 25448 KB Output isn't correct
14 Incorrect 232 ms 26324 KB Output isn't correct
15 Incorrect 213 ms 28684 KB Output isn't correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1054 ms 31260 KB Output isn't correct
2 Incorrect 1255 ms 30348 KB Output isn't correct
3 Incorrect 1976 ms 37428 KB Output isn't correct
4 Incorrect 182 ms 28316 KB Output isn't correct
5 Incorrect 237 ms 30888 KB Output isn't correct
6 Incorrect 392 ms 30212 KB Output isn't correct
7 Incorrect 544 ms 30528 KB Output isn't correct
8 Incorrect 759 ms 39912 KB Output isn't correct
9 Incorrect 1557 ms 49040 KB Output isn't correct
10 Incorrect 3088 ms 57564 KB Output isn't correct
11 Incorrect 4078 ms 55952 KB Output isn't correct
12 Incorrect 1293 ms 44228 KB Output isn't correct
13 Incorrect 1919 ms 48016 KB Output isn't correct
14 Incorrect 2116 ms 50816 KB Output isn't correct
15 Incorrect 3107 ms 59912 KB Output isn't correct
16 Incorrect 2695 ms 66484 KB Output isn't correct
17 Incorrect 2607 ms 63976 KB Output isn't correct