제출 #411732

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
411732		AugustinasJucas	Regions (IOI09_regions)	C++14	85 / 100	2931 ms	75880 KiB

regions

#include <bits/stdc++.h>
#pragma GCC optimize("O2")
#pragma GCC target("avx2")
using namespace std;
const int inf = 1e9;
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];
vector<pair<int, int> > regs1[dydis], regs2[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 = 1;
int kelint[dydis];
int enter[dydis], leave[dydis];
long long dideliuMem1[450][20001] = {}, dideliuMem2[450][20001] = {};
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);
}
int kr[dydis] = {0};
long long daryk(int a, int b){
    auto &virs = regs2[a];
    auto &apac = regs1[b];
    vector<pair<int, int> > srt;
    int i1 = 0;
    int i2 = 0;
    int sm = 0;
    long long ans = 0;
    while(i1 != virs.size() || i2 != apac.size()){
        if(i1 == virs.size()){ 
            auto &st = apac[i2++];
            sm++;
        }else if(i2 == apac.size()){
            auto &st = virs[i1++];
            if(st.second < 0){
                kr[-st.second] = sm;
            }else{
                ans += sm - kr[st.second];
            }
        }else if(virs[i1] < apac[i2]){
            auto &st = virs[i1++];
            if(st.second < 0){
                kr[-st.second] = sm;
            }else{
                ans += sm - kr[st.second];
            }
        }else{
            auto &st = apac[i2++];
            sm++;
        }
    }
    return ans;
}
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;
    ret = daryk(a, b);	
	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);
    for(int i = 0; i < r; i++){
        for(auto x : regs[i]){
            regs1[i].push_back({enter[x], -inf});
            regs2[i].push_back({enter[x], -x});
            regs2[i].push_back({leave[x], x});
        }
        sort(regs1[i].begin(), regs1[i].end());
        sort(regs2[i].begin(), regs2[i].end());
    }
	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;
}

컴파일 시 표준 에러 (stderr) 메시지

regions.cpp: In function 'long long int daryk(int, int)':
regions.cpp:116:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |     while(i1 != virs.size() || i2 != apac.size()){
      |           ~~~^~~~~~~~~~~~~~
regions.cpp:116:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |     while(i1 != virs.size() || i2 != apac.size()){
      |                                ~~~^~~~~~~~~~~~~~
regions.cpp:117:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |         if(i1 == virs.size()){
      |            ~~~^~~~~~~~~~~~~~
regions.cpp:118:19: warning: unused variable 'st' [-Wunused-variable]
  118 |             auto &st = apac[i2++];
      |                   ^~
regions.cpp:120:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |         }else if(i2 == apac.size()){
      |                  ~~~^~~~~~~~~~~~~~
regions.cpp:135:19: warning: unused variable 'st' [-Wunused-variable]
  135 |             auto &st = apac[i2++];
      |                   ^~

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