oj.uz

답안 #411530

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
411530 2021-05-25T13:16:29 Z AugustinasJucas Regions (IOI09_regions) C++14
0 / 100
 8000 ms 32888 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)-100;
	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 8 ms 9672 KB Output isn't correct
4 Incorrect 12 ms 9624 KB Output isn't correct
5 Incorrect 16 ms 9672 KB Output isn't correct
6 Incorrect 32 ms 9800 KB Output isn't correct
7 Incorrect 31 ms 9800 KB Output isn't correct
8 Incorrect 45 ms 9800 KB Output isn't correct
9 Incorrect 60 ms 10184 KB Output isn't correct
10 Incorrect 73 ms 10184 KB Output isn't correct
11 Incorrect 103 ms 10448 KB Output isn't correct
12 Incorrect 161 ms 11008 KB Output isn't correct
13 Incorrect 77 ms 10952 KB Output isn't correct
14 Incorrect 195 ms 11336 KB Output isn't correct
15 Incorrect 118 ms 13640 KB Output isn't correct

Subtask #2
0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 907 ms 14280 KB Output isn't correct
2 Incorrect 906 ms 14144 KB Output isn't correct
3 Incorrect 1468 ms 15936 KB Output isn't correct
4 Incorrect 245 ms 11684 KB Output isn't correct
5 Incorrect 424 ms 14184 KB Output isn't correct
6 Incorrect 697 ms 13968 KB Output isn't correct
7 Incorrect 1068 ms 14420 KB Output isn't correct
8 Incorrect 1060 ms 19516 KB Output isn't correct
9 Incorrect 5018 ms 21376 KB Output isn't correct
10 Incorrect 6219 ms 26032 KB Output isn't correct
11 Execution timed out 8087 ms 23368 KB Time limit exceeded
12 Incorrect 5459 ms 21820 KB Output isn't correct
13 Incorrect 7900 ms 23592 KB Output isn't correct
14 Incorrect 6019 ms 23744 KB Output isn't correct
15 Execution timed out 8071 ms 26644 KB Time limit exceeded
16 Execution timed out 8073 ms 32164 KB Time limit exceeded
17 Execution timed out 8009 ms 32888 KB Time limit exceeded