oj.uz

답안 #411527

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
411527 2021-05-25T13:10:20 Z AugustinasJucas Regions (IOI09_regions) C++14
26 / 100
 8000 ms 32936 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);
	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
11.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 9672 KB Output isn't correct
2 Incorrect 6 ms 9672 KB Output isn't correct
3 Correct 9 ms 9672 KB Output is correct
4 Correct 11 ms 9672 KB Output is correct
5 Correct 13 ms 9852 KB Output is correct
6 Correct 32 ms 9832 KB Output is correct
7 Correct 47 ms 9860 KB Output is correct
8 Correct 55 ms 9980 KB Output is correct
9 Correct 62 ms 10392 KB Output is correct
10 Correct 90 ms 10548 KB Output is correct
11 Correct 225 ms 10836 KB Output is correct
12 Correct 214 ms 11528 KB Output is correct
13 Correct 390 ms 11564 KB Output is correct
14 Incorrect 982 ms 11828 KB Output isn't correct
15 Incorrect 921 ms 14432 KB Output isn't correct

Subtask #2
15.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3581 ms 15200 KB Output isn't correct
2 Incorrect 4937 ms 15216 KB Output isn't correct
3 Execution timed out 8032 ms 18532 KB Time limit exceeded
4 Correct 453 ms 12608 KB Output is correct
5 Correct 530 ms 14252 KB Output is correct
6 Incorrect 551 ms 13888 KB Output isn't correct
7 Incorrect 838 ms 14492 KB Output isn't correct
8 Incorrect 879 ms 19496 KB Output isn't correct
9 Correct 6797 ms 24376 KB Output is correct
10 Incorrect 6420 ms 25960 KB Output isn't correct
11 Execution timed out 8093 ms 23384 KB Time limit exceeded
12 Incorrect 5336 ms 21956 KB Output isn't correct
13 Execution timed out 8037 ms 23444 KB Time limit exceeded
14 Incorrect 6307 ms 23816 KB Output isn't correct
15 Execution timed out 8019 ms 26604 KB Time limit exceeded
16 Execution timed out 8016 ms 31992 KB Time limit exceeded
17 Execution timed out 8035 ms 32936 KB Time limit exceeded