oj.uz

Submission #524529

# Submission time Handle Problem Language Result Execution time Memory
524529 2022-02-09T12:19:46 Z AmirElarbi Regions (IOI09_regions) C++14
95 / 100
 3400 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;
const int nax2 = 3e4;
vi adj[nax], node;
int a[nax], tin[nax],tout[nax], cnt = 0, vis[nax2],freq[nax];
vi v[nax2];
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 7880 KB Output is correct
2 Correct 4 ms 7112 KB Output is correct
3 Correct 6 ms 7112 KB Output is correct
4 Correct 9 ms 7112 KB Output is correct
5 Correct 11 ms 7112 KB Output is correct
6 Correct 24 ms 7112 KB Output is correct
7 Correct 31 ms 7112 KB Output is correct
8 Correct 32 ms 7240 KB Output is correct
9 Correct 56 ms 7624 KB Output is correct
10 Correct 94 ms 7624 KB Output is correct
11 Correct 128 ms 7880 KB Output is correct
12 Correct 148 ms 8392 KB Output is correct
13 Correct 169 ms 8420 KB Output is correct
14 Correct 254 ms 9544 KB Output is correct
15 Correct 299 ms 11992 KB Output is correct

Subtask #2
80.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1715 ms 12708 KB Output is correct
2 Correct 1930 ms 12432 KB Output is correct
3 Correct 2549 ms 14264 KB Output is correct
4 Correct 194 ms 9004 KB Output is correct
5 Correct 355 ms 10272 KB Output is correct
6 Correct 677 ms 28260 KB Output is correct
7 Correct 1326 ms 35512 KB Output is correct
8 Correct 1795 ms 63540 KB Output is correct
9 Correct 2105 ms 16316 KB Output is correct
10 Runtime error 1905 ms 131076 KB Execution killed with signal 9
11 Correct 3400 ms 18528 KB Output is correct
12 Correct 1384 ms 19512 KB Output is correct
13 Correct 1883 ms 20260 KB Output is correct
14 Correct 2352 ms 36636 KB Output is correct
15 Correct 3050 ms 24496 KB Output is correct
16 Correct 2918 ms 30000 KB Output is correct
17 Correct 3014 ms 45244 KB Output is correct