oj.uz

Submission #524530

# Submission time Handle Problem Language Result Execution time Memory
524530 2022-02-09T12:22:02 Z AmirElarbi Regions (IOI09_regions) C++14
100 / 100
 3485 ms 128744 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+10;
const int nax2 = 3e4;
vi adj[nax], node;
int a[nax], tin[nax],tout[nax], cnt = 0, vis[nax2],freq[nax];
vi v[nax2];
unordered_map<int,int> res[nax2];
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:57:33: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   57 |         if(v[a[node[i]]].size() <= mxk) continue;
      |            ~~~~~~~~~~~~~~~~~~~~~^~~~~~
regions.cpp:75:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   75 |         if(v[xu].size() <= mxk){
      |            ~~~~~~~~~~~~~^~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8136 KB Output is correct
2 Correct 4 ms 7368 KB Output is correct
3 Correct 7 ms 7368 KB Output is correct
4 Correct 8 ms 7368 KB Output is correct
5 Correct 10 ms 7328 KB Output is correct
6 Correct 18 ms 7368 KB Output is correct
7 Correct 32 ms 7368 KB Output is correct
8 Correct 30 ms 7496 KB Output is correct
9 Correct 50 ms 7880 KB Output is correct
10 Correct 61 ms 7928 KB Output is correct
11 Correct 109 ms 8120 KB Output is correct
12 Correct 147 ms 8648 KB Output is correct
13 Correct 163 ms 8688 KB Output is correct
14 Correct 243 ms 9812 KB Output is correct
15 Correct 203 ms 12168 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1538 ms 12940 KB Output is correct
2 Correct 1882 ms 12600 KB Output is correct
3 Correct 2401 ms 14580 KB Output is correct
4 Correct 234 ms 9132 KB Output is correct
5 Correct 341 ms 10564 KB Output is correct
6 Correct 509 ms 27708 KB Output is correct
7 Correct 970 ms 31940 KB Output is correct
8 Correct 1264 ms 56232 KB Output is correct
9 Correct 2131 ms 16540 KB Output is correct
10 Correct 3485 ms 128744 KB Output is correct
11 Correct 3442 ms 18740 KB Output is correct
12 Correct 1376 ms 19644 KB Output is correct
13 Correct 1497 ms 20368 KB Output is correct
14 Correct 2282 ms 34612 KB Output is correct
15 Correct 2832 ms 24624 KB Output is correct
16 Correct 3164 ms 30156 KB Output is correct
17 Correct 2876 ms 42984 KB Output is correct