oj.uz

답안 #411538

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
411538 2021-05-25T13:22:22 Z AugustinasJucas Regions (IOI09_regions) C++14
0 / 100
 8000 ms 32892 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 0;
		return dideliuMem1[sk][b];
	}
	if((int)regs[b].size() >= sq){
		int sk = kelint[b];
        return 0;
		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)-200;
	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:85:10: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   85 | int main(){
      |          ^

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 9672 KB Output isn't correct
2 Incorrect 7 ms 9672 KB Output isn't correct
3 Incorrect 7 ms 9672 KB Output isn't correct
4 Incorrect 9 ms 9672 KB Output isn't correct
5 Incorrect 15 ms 9672 KB Output isn't correct
6 Incorrect 30 ms 9700 KB Output isn't correct
7 Incorrect 47 ms 9800 KB Output isn't correct
8 Incorrect 57 ms 9800 KB Output isn't correct
9 Incorrect 68 ms 10184 KB Output isn't correct
10 Incorrect 99 ms 10184 KB Output isn't correct
11 Incorrect 116 ms 10440 KB Output isn't correct
12 Incorrect 113 ms 10952 KB Output isn't correct
13 Incorrect 169 ms 10980 KB Output isn't correct
14 Incorrect 149 ms 11336 KB Output isn't correct
15 Incorrect 261 ms 13736 KB Output isn't correct

Subtask #2
0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 803 ms 14212 KB Output isn't correct
2 Incorrect 999 ms 14084 KB Output isn't correct
3 Incorrect 1183 ms 15956 KB Output isn't correct
4 Incorrect 309 ms 11504 KB Output isn't correct
5 Incorrect 425 ms 12944 KB Output isn't correct
6 Incorrect 488 ms 13976 KB Output isn't correct
7 Incorrect 806 ms 14132 KB Output isn't correct
8 Incorrect 963 ms 19488 KB Output isn't correct
9 Incorrect 4367 ms 20604 KB Output isn't correct
10 Incorrect 6514 ms 25872 KB Output isn't correct
11 Incorrect 5136 ms 23792 KB Output isn't correct
12 Incorrect 5510 ms 21588 KB Output isn't correct
13 Execution timed out 8084 ms 23496 KB Time limit exceeded
14 Incorrect 6302 ms 23652 KB Output isn't correct
15 Execution timed out 8005 ms 26624 KB Time limit exceeded
16 Execution timed out 8013 ms 32036 KB Time limit exceeded
17 Execution timed out 8037 ms 32892 KB Time limit exceeded