Submission #524527

#	Time	Username	Problem	Language	Result	Execution time	Memory
524527		AmirElarbi	Regions (IOI09_regions)	C++14	0 / 100	28 ms	38676 KiB

regions

#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;
    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
    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 (stderr)

regions.cpp: In function 'int main()':
regions.cpp:60:33: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   60 |         if(v[a[node[i]]].size() <= mxk) continue;
      |            ~~~~~~~~~~~~~~~~~~~~~^~~~~~
regions.cpp:78:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   78 |         if(v[xu].size() <= mxk){
      |            ~~~~~~~~~~~~~^~~~~~
regions.cpp:39:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |         freopen("input.txt", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:40:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |         freopen("output.txt", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 15
• Subtask 2: 0 / 85