oj.uz

답안 #411711

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
411711 2021-05-25T18:43:31 Z AugustinasJucas Regions (IOI09_regions) C++14
50 / 100
 8000 ms 53320 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O2")
#pragma GCC target("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) + 30 ;
	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;
}

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 14408 KB Output is correct
2 Correct 11 ms 14388 KB Output is correct
3 Correct 15 ms 14408 KB Output is correct
4 Correct 18 ms 14456 KB Output is correct
5 Correct 20 ms 14476 KB Output is correct
6 Correct 35 ms 14532 KB Output is correct
7 Correct 63 ms 14536 KB Output is correct
8 Correct 74 ms 14580 KB Output is correct
9 Correct 129 ms 15296 KB Output is correct
10 Correct 217 ms 15248 KB Output is correct
11 Correct 513 ms 15584 KB Output is correct
12 Correct 568 ms 16292 KB Output is correct
13 Correct 812 ms 16328 KB Output is correct
14 Correct 1500 ms 16692 KB Output is correct
15 Correct 1976 ms 19176 KB Output is correct

Subtask #2
35.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4352 ms 21100 KB Output is correct
2 Correct 5765 ms 20856 KB Output is correct
3 Execution timed out 8074 ms 24416 KB Time limit exceeded
4 Correct 1499 ms 17316 KB Output is correct
5 Correct 1442 ms 18992 KB Output is correct
6 Correct 899 ms 26452 KB Output is correct
7 Correct 1805 ms 28284 KB Output is correct
8 Correct 2310 ms 42792 KB Output is correct
9 Execution timed out 8052 ms 26200 KB Time limit exceeded
10 Execution timed out 8082 ms 53320 KB Time limit exceeded
11 Execution timed out 8023 ms 27580 KB Time limit exceeded
12 Execution timed out 8042 ms 28312 KB Time limit exceeded
13 Execution timed out 8032 ms 29584 KB Time limit exceeded
14 Execution timed out 8019 ms 36476 KB Time limit exceeded
15 Execution timed out 8070 ms 33344 KB Time limit exceeded
16 Execution timed out 8071 ms 40956 KB Time limit exceeded
17 Execution timed out 8074 ms 46780 KB Time limit exceeded