oj.uz

답안 #411526

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
411526 2021-05-25T13:09:16 Z AugustinasJucas Regions (IOI09_regions) C++14
65 / 100
 8000 ms 60220 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O2")
#pragma GCC optimize("avx2")
using namespace std;
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];
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[a]){
		for(auto y : regs[b]){
			ret += isAnc(x, y);
		}
	}
	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

regions.cpp:3:28: warning: bad option '-favx2' to pragma 'optimize' [-Wpragmas]
    3 | #pragma GCC optimize("avx2")
      |                            ^
regions.cpp:20:26: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   20 | void dfs1(int v, int came){
      |                          ^
regions.cpp:28:24: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   28 | bool isAnc(int a, int b){
      |                        ^
regions.cpp:33:15: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   33 | void dfs(int v){
      |               ^
regions.cpp:52:18: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   52 | void calc(int ind){
      |                  ^
regions.cpp:63:25: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   63 | long long f(int a, int b){
      |                         ^
regions.cpp:83:10: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   83 | int main(){
      |          ^

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 9672 KB Output is correct
2 Correct 7 ms 9672 KB Output is correct
3 Correct 8 ms 9672 KB Output is correct
4 Correct 9 ms 9672 KB Output is correct
5 Correct 17 ms 9832 KB Output is correct
6 Correct 27 ms 9832 KB Output is correct
7 Correct 36 ms 9976 KB Output is correct
8 Correct 45 ms 9908 KB Output is correct
9 Correct 53 ms 10332 KB Output is correct
10 Correct 127 ms 10676 KB Output is correct
11 Correct 175 ms 11124 KB Output is correct
12 Correct 247 ms 11496 KB Output is correct
13 Correct 396 ms 11612 KB Output is correct
14 Correct 900 ms 12172 KB Output is correct
15 Correct 840 ms 15336 KB Output is correct

Subtask #2
50.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3480 ms 16236 KB Output is correct
2 Correct 5177 ms 16096 KB Output is correct
3 Execution timed out 8025 ms 20060 KB Time limit exceeded
4 Correct 316 ms 12700 KB Output is correct
5 Correct 450 ms 14376 KB Output is correct
6 Correct 953 ms 21592 KB Output is correct
7 Correct 1205 ms 23388 KB Output is correct
8 Correct 1436 ms 37840 KB Output is correct
9 Correct 6329 ms 24516 KB Output is correct
10 Incorrect 6749 ms 60220 KB Output isn't correct
11 Execution timed out 8010 ms 23584 KB Time limit exceeded
12 Correct 5717 ms 23836 KB Output is correct
13 Execution timed out 8076 ms 25868 KB Time limit exceeded
14 Correct 6757 ms 32388 KB Output is correct
15 Execution timed out 8071 ms 29964 KB Time limit exceeded
16 Execution timed out 8028 ms 37292 KB Time limit exceeded
17 Execution timed out 8004 ms 44292 KB Time limit exceeded