답안 #411731

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
411731 2021-05-25T19:46:55 Z AugustinasJucas Regions (IOI09_regions) C++14
85 / 100
2924 ms 76236 KB
#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;
}

Compilation message

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++];
      |                   ^~
# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 19144 KB Output is correct
2 Correct 12 ms 19144 KB Output is correct
3 Correct 13 ms 19136 KB Output is correct
4 Correct 18 ms 19148 KB Output is correct
5 Correct 21 ms 19144 KB Output is correct
6 Correct 34 ms 19264 KB Output is correct
7 Correct 48 ms 19392 KB Output is correct
8 Correct 47 ms 19356 KB Output is correct
9 Correct 43 ms 19996 KB Output is correct
10 Correct 123 ms 20328 KB Output is correct
11 Correct 143 ms 20804 KB Output is correct
12 Correct 153 ms 21824 KB Output is correct
13 Correct 220 ms 21948 KB Output is correct
14 Correct 147 ms 23004 KB Output is correct
15 Correct 297 ms 26440 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1102 ms 28124 KB Output is correct
2 Correct 1310 ms 28140 KB Output is correct
3 Correct 1772 ms 32424 KB Output is correct
4 Correct 187 ms 23292 KB Output is correct
5 Correct 370 ms 25016 KB Output is correct
6 Correct 766 ms 32812 KB Output is correct
7 Correct 782 ms 35580 KB Output is correct
8 Correct 1290 ms 50836 KB Output is correct
9 Correct 1850 ms 40652 KB Output is correct
10 Incorrect 2222 ms 76236 KB Output isn't correct
11 Correct 2924 ms 47696 KB Output is correct
12 Correct 1389 ms 39580 KB Output is correct
13 Correct 1734 ms 41976 KB Output is correct
14 Correct 2505 ms 48968 KB Output is correct
15 Incorrect 2470 ms 49140 KB Output isn't correct
16 Incorrect 2402 ms 55320 KB Output isn't correct
17 Correct 2614 ms 61100 KB Output is correct