Submission #411699

#	Time	Username	Problem	Language	Result	Execution time	Memory
411699		AugustinasJucas	Regions (IOI09_regions)	C++14	50 / 100	8087 ms	64540 KiB

regions

#include <bits/stdc++.h>
#pragma GCC optimize("O2")
#pragma GCC optimize("avx2")
using namespace std;
struct medis{
    struct node{
        int l, r, val = 0;
    };
    vector<node> tree;
    int n;
    int dbInd = 0;
    void build(int v){
        if(v >= n){
            tree[v].l = tree[v].r = dbInd++;
        }else{
            build(v*2); build(v*2+1);
            tree[v].l = tree[v*2].l;
            tree[v].r = tree[v*2+1].r; 
        }
    }
    medis(int dd){
        n = dd;
        tree.resize(n * 2 + 1);
        build(1);
    }
    void change(int v, int l, int r, int x){
        if(l <= tree[v].l && tree[v].r <= r){
            tree[v].val = x;
        }else if(r < tree[v].l || tree[v].r < l){
        
        }else{
            change(v*2, l, r, x);
            change(v*2+1, l, r, x);
            tree[v].val = tree[v*2].val + tree[v*2+1].val;
        }
    }
    int get(int v, int l, int r){
        if(l <= tree[v].l && tree[v].r <= r){
            return tree[v].val;
        }else if(r < tree[v].l || tree[v].r < l){
            return 0;
        }else{
            return get(v*2, l, r) + get(v*2+1, l, r);
        }
    }
};
const int dydis = 2e5 + 10;
int n, r, q;
vector<int> dideli; // regionai
vector<int> regs[dydis];
int tevas[dydis];
vector<int> gr[dydis];
unordered_map<long long, long long > rem;
int sm[dydis];
int val[dydis];
int kam[dydis];
int sq;
int dbInd = 0;
int kelint[dydis];
int enter[dydis], leave[dydis];
long long dideliuMem1[450][20001], dideliuMem2[450][20001];
medis tree(dydis);
void dfs1(int v, int came){
	enter[v] = dbInd++;
	for(auto x : gr[v]){
		if(x == came) continue;
		dfs1(x, v);
	}
	leave[v] = dbInd;
}
bool isAnc(int a, int b){
	return enter[a] <= enter[b] && leave[b] <= leave[a];
}
int kek = 0;
int prm = 0;
void dfs(int v){
//		cout << "v = " << v << endl;
	sm[v] = val[v];
	for(auto x : gr[v]){
		if(x == tevas[v]) continue;
		kek += val[v];
        dfs(x);
        kek -= val[v];
		sm[v] += sm[x];
	}
 
	if(!val[v]){
//		cout << "rem[" << prm+1 << "][" << v+1 << "(" << kam[v]+1 << ")] += " << kek << "\n";
//		cout << "rem[" << v+1 << "(" << kam[v]+1 << ")][" << prm+1 << "] += " << sm[v] << "\n"
		dideliuMem1[prm][kam[v]] += kek;
		dideliuMem2[prm][kam[v]] += sm[v];
	}
}
int dbIndd = 0;
void calc(int ind){
	kelint[ind] = dbIndd++;
//	cout << "nuo " << ind+1 << endl;
	for(int i = 0; i < n; i++) sm[i] = val[i] = 0;
	for(auto x : regs[ind]){
		val[x] = 1;
	}
    kek = 0;
    prm = dbIndd-1;
	dfs(0);
}
long long f(int a, int b){
	if((int)regs[a].size() >= sq){
		int sk = kelint[a];
		return dideliuMem1[sk][b];
	}
	if((int)regs[b].size() >= sq){
		int sk = kelint[b];
		return dideliuMem2[sk][a];
	}
	if(rem.count(a*dydis+b)) {
		return rem[a*dydis+b] ;
	}
	long long ret = 0;
	for(auto x : regs[b]){
        tree.change(1, enter[x], enter[x], 1);
    }
    for(auto x : regs[a]){
        ret += tree.get(1, enter[x], leave[x]-1);
    }
    for(auto x : regs[b]){
	    tree.change(1, enter[x], enter[x], 0);
    }
	return rem[a*dydis+b] = ret;
}
int main(){
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	cin >> n >> r >> q;
	for(int i = 0; i < n; i++){
		int par = -1, reg;
		if(i == 0) cin >> reg;
		else cin >> par >> reg;
		par--; reg--;
		regs[reg].push_back(i);
		if(par != -2){
			gr[i].push_back(par);
			gr[par].push_back(i);
		}
		tevas[i] = par;
		kam[i] = reg;
	}
	dfs1(0, -1);
	sq = sqrt(n) ;
	for(int i = 0; i < r; i++){
		if((int)regs[i].size() >= sq){
			calc(i);
			dideli.push_back(i);
		}
	}
	while(q--){
		int a, b; cin >> a >> b; a--; b--;
		cout << f(a, b) << endl;
	}
	return 0;
}

Compilation message (stderr)

regions.cpp:3:28: warning: bad option '-favx2' to pragma 'optimize' [-Wpragmas]
    3 | #pragma GCC optimize("avx2")
      |                            ^
regions.cpp:12:21: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   12 |     void build(int v){
      |                     ^
regions.cpp:21:17: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   21 |     medis(int dd){
      |                 ^
regions.cpp:26:43: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   26 |     void change(int v, int l, int r, int x){
      |                                           ^
regions.cpp:37:32: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   37 |     int get(int v, int l, int r){
      |                                ^
regions.cpp:63:26: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   63 | void dfs1(int v, int came){
      |                          ^
regions.cpp:71:24: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   71 | bool isAnc(int a, int b){
      |                        ^
regions.cpp:76:15: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   76 | void dfs(int v){
      |               ^
regions.cpp:95:18: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   95 | void calc(int ind){
      |                  ^
regions.cpp:106:25: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
  106 | long long f(int a, int b){
      |                         ^
regions.cpp:130:10: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
  130 | int main(){
      |          ^

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