답안 #411732

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
411732 2021-05-25T19:51:45 Z AugustinasJucas Regions (IOI09_regions) C++14
85 / 100
2931 ms 75880 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 12 ms 19144 KB Output is correct
2 Correct 12 ms 19132 KB Output is correct
3 Correct 15 ms 19016 KB Output is correct
4 Correct 17 ms 19144 KB Output is correct
5 Correct 21 ms 19108 KB Output is correct
6 Correct 38 ms 19268 KB Output is correct
7 Correct 42 ms 19396 KB Output is correct
8 Correct 45 ms 19444 KB Output is correct
9 Correct 75 ms 19920 KB Output is correct
10 Correct 127 ms 20288 KB Output is correct
11 Correct 123 ms 20992 KB Output is correct
12 Correct 136 ms 21664 KB Output is correct
13 Correct 131 ms 22032 KB Output is correct
14 Correct 198 ms 22964 KB Output is correct
15 Correct 257 ms 26372 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1057 ms 28192 KB Output is correct
2 Correct 1020 ms 28184 KB Output is correct
3 Correct 1804 ms 32700 KB Output is correct
4 Correct 280 ms 23232 KB Output is correct
5 Correct 392 ms 25012 KB Output is correct
6 Correct 747 ms 32876 KB Output is correct
7 Correct 1042 ms 35732 KB Output is correct
8 Correct 1268 ms 50960 KB Output is correct
9 Correct 2013 ms 40268 KB Output is correct
10 Incorrect 2243 ms 75880 KB Output isn't correct
11 Correct 2931 ms 47732 KB Output is correct
12 Correct 1151 ms 39736 KB Output is correct
13 Correct 1754 ms 41864 KB Output is correct
14 Correct 2264 ms 49100 KB Output is correct
15 Incorrect 2601 ms 49148 KB Output isn't correct
16 Incorrect 2383 ms 55216 KB Output isn't correct
17 Correct 2464 ms 61124 KB Output is correct