oj.uz

답안 #411523

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
411523 2021-05-25T13:07:05 Z AugustinasJucas Regions (IOI09_regions) C++14
65 / 100
 8000 ms 61336 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];
map<pair<int, int>, 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, b})) {
		return rem[{a, b}] ;
	}
	long long ret = 0;
	for(auto x : regs[a]){
		for(auto y : regs[b]){
			ret += isAnc(x, y);
		}
	}
	return rem[{a, 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:21:26: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   21 | void dfs1(int v, int came){
      |                          ^
regions.cpp:29:24: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   29 | bool isAnc(int a, int b){
      |                        ^
regions.cpp:34:15: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   34 | void dfs(int v){
      |               ^
regions.cpp:53:18: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   53 | void calc(int ind){
      |                  ^
regions.cpp:64:25: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   64 | long long f(int a, int b){
      |                         ^
regions.cpp:84:10: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   84 | 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 10 ms 9672 KB Output is correct
4 Correct 12 ms 9744 KB Output is correct
5 Correct 14 ms 9800 KB Output is correct
6 Correct 31 ms 10040 KB Output is correct
7 Correct 32 ms 9884 KB Output is correct
8 Correct 44 ms 10004 KB Output is correct
9 Correct 88 ms 10500 KB Output is correct
10 Correct 127 ms 10708 KB Output is correct
11 Correct 250 ms 11052 KB Output is correct
12 Correct 242 ms 11676 KB Output is correct
13 Correct 461 ms 11760 KB Output is correct
14 Correct 990 ms 12300 KB Output is correct
15 Correct 909 ms 15640 KB Output is correct

Subtask #2
50.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3236 ms 16812 KB Output is correct
2 Correct 4947 ms 16452 KB Output is correct
3 Execution timed out 8077 ms 21200 KB Time limit exceeded
4 Correct 452 ms 13036 KB Output is correct
5 Correct 460 ms 14992 KB Output is correct
6 Correct 692 ms 21976 KB Output is correct
7 Correct 1194 ms 24092 KB Output is correct
8 Correct 1243 ms 38360 KB Output is correct
9 Correct 6207 ms 27148 KB Output is correct
10 Incorrect 7301 ms 61336 KB Output isn't correct
11 Execution timed out 8010 ms 24228 KB Time limit exceeded
12 Correct 5654 ms 24568 KB Output is correct
13 Execution timed out 8007 ms 26968 KB Time limit exceeded
14 Correct 7237 ms 33800 KB Output is correct
15 Execution timed out 8064 ms 31168 KB Time limit exceeded
16 Execution timed out 8061 ms 38452 KB Time limit exceeded
17 Execution timed out 8064 ms 44848 KB Time limit exceeded