oj.uz

Submission #524528

# Submission time Handle Problem Language Result Execution time Memory
524528 2022-02-09T12:15:58 Z AmirElarbi Regions (IOI09_regions) C++14
95 / 100
 3550 ms 131076 KB 
#include <bits/stdc++.h>
#define vi vector<int>
#define ve vector
#define ll long long
#define vf vector<float>
#define vll vector<pair<ll,ll>>
#define ii pair<int,int>
#define vvi vector<vi>
#define vii vector<ii>
#define gii greater<ii>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define INF 1e9
#define eps 1e-7
#define eps1 1e-2
#define optimise ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MAX_A 1e5+5
#define V 450
using namespace std;
const int MOD = 1e9+7;
const int nax = 2e5+5;
vi adj[nax], node;
int a[nax], tin[nax],tout[nax], cnt = 0, vis[nax],freq[nax];
vi v[nax];
map<int,int> res[nax];
void dfs(int u, int p){
    node.pb(u);
    tin[u] = cnt;
    cnt++;
    for(auto x : adj[u])
        if(p != x) dfs(x,u);
    tout[u] = cnt-1;
}
int main(){ 
    optimise;
    int n,r,q;
    cin >> n >> r >> q >> a[0];
    for (int i = 1; i < n; ++i)
    {
        int b;
        cin >> b >> a[i]; 
        b--;
        adj[i].pb(b), adj[b].pb(i);
    }
    dfs(0,0);
    for (int i = 0; i < n; ++i)
    {
        v[a[node[i]]].pb(i);
    }
    int mxk = sqrt(n);
    for (int i = 0; i < n; ++i)
    {
        if(vis[a[node[i]]]) continue;
        if(v[a[node[i]]].size() <= mxk) continue;
        vis[a[node[i]]] = 1;
        memset(freq,0,sizeof freq);
        for(auto x : v[a[node[i]]]){
            int l = tin[node[x]], r = tout[node[x]];
            freq[l]++, freq[r+1]--;
        }
        res[a[node[i]]][a[node[0]]] += freq[0]; 
        for (int j = 1; j < n; ++j)
        {
            freq[j] += freq[j-1];
            res[a[node[i]]][a[node[j]]] += freq[j]; 
        }
    }
    for (int i = 0; i < q; ++i)
    {
        int xu,xv, ans = 0;
        cin >> xu >> xv;
        if(v[xu].size() <= mxk){
            for(auto x : v[xu]){
                int l = tin[node[x]], r = tout[node[x]]; 
                int p1 = upper_bound(v[xv].begin(), v[xv].end(), r) - v[xv].begin(),
                    p2 = upper_bound(v[xv].begin(), v[xv].end(), l)- v[xv].begin();
                
                if(p1) p1--, ans += max(p1-p2+1,0);
            }
        }else ans = res[xu][xv];
        cout << ans << endl;
    }
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:56:33: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   56 |         if(v[a[node[i]]].size() <= mxk) continue;
      |            ~~~~~~~~~~~~~~~~~~~~~^~~~~~
regions.cpp:74:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   74 |         if(v[xu].size() <= mxk){
      |            ~~~~~~~~~~~~~^~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19784 KB Output is correct
2 Correct 10 ms 19028 KB Output is correct
3 Correct 12 ms 19016 KB Output is correct
4 Correct 11 ms 19016 KB Output is correct
5 Correct 17 ms 19144 KB Output is correct
6 Correct 23 ms 19172 KB Output is correct
7 Correct 36 ms 19144 KB Output is correct
8 Correct 37 ms 19144 KB Output is correct
9 Correct 49 ms 19612 KB Output is correct
10 Correct 95 ms 19656 KB Output is correct
11 Correct 128 ms 19912 KB Output is correct
12 Correct 129 ms 20408 KB Output is correct
13 Correct 186 ms 20376 KB Output is correct
14 Correct 274 ms 21564 KB Output is correct
15 Correct 304 ms 23892 KB Output is correct

Subtask #2
80.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1598 ms 24592 KB Output is correct
2 Correct 2067 ms 24384 KB Output is correct
3 Correct 2724 ms 26292 KB Output is correct
4 Correct 224 ms 20892 KB Output is correct
5 Correct 347 ms 22308 KB Output is correct
6 Correct 843 ms 40356 KB Output is correct
7 Correct 1395 ms 47516 KB Output is correct
8 Correct 1915 ms 75516 KB Output is correct
9 Correct 2168 ms 28340 KB Output is correct
10 Runtime error 1687 ms 131076 KB Execution killed with signal 9
11 Correct 3550 ms 30556 KB Output is correct
12 Correct 1426 ms 31468 KB Output is correct
13 Correct 1854 ms 32184 KB Output is correct
14 Correct 2587 ms 48636 KB Output is correct
15 Correct 2705 ms 36496 KB Output is correct
16 Correct 3095 ms 41968 KB Output is correct
17 Correct 3158 ms 57228 KB Output is correct