답안 #411709

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
411709 2021-05-25T18:35:18 Z AugustinasJucas Regions (IOI09_regions) C++14
45 / 100
8000 ms 44720 KB
#include <bits/stdc++.h>
#pragma GCC optimize("O2")
#pragma GCC optimize("avx2")
using namespace std;
struct medis{
    struct node{
        int l, r, val = 0;
    };
    vector<node> tree;
    int n;
    int dbInd = 0;
    void build(int v){
        if(v >= n){
            tree[v].l = tree[v].r = dbInd++;
        }else{
            build(v*2); build(v*2+1);
            tree[v].l = tree[v*2].l;
            tree[v].r = tree[v*2+1].r; 
        }
    }
    medis(int dd){
        n = dd;
        tree.resize(n * 2 + 1);
        build(1);
    }
    void change(int v, int l, int r, int x){
        if(l <= tree[v].l && tree[v].r <= r){
            tree[v].val = x;
        }else if(r < tree[v].l || tree[v].r < l){
        
        }else{
            change(v*2, l, r, x);
            change(v*2+1, l, r, x);
            tree[v].val = tree[v*2].val + tree[v*2+1].val;
        }
    }
    int get(int v, int l, int r){
        if(l <= tree[v].l && tree[v].r <= r){
            return tree[v].val;
        }else if(r < tree[v].l || tree[v].r < l){
            return 0;
        }else{
            return get(v*2, l, r) + get(v*2+1, l, r);
        }
    }
};
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];
medis tree(dydis);
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[b]){
        tree.change(1, enter[x], enter[x], 1);
    }
    for(auto x : regs[a]){
        ret += tree.get(1, enter[x], leave[x]-1);
    }
    for(auto x : regs[b]){
	    tree.change(1, enter[x], enter[x], 0);
    }
	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) + 300 ;
	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:12:21: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   12 |     void build(int v){
      |                     ^
regions.cpp:21:17: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   21 |     medis(int dd){
      |                 ^
regions.cpp:26:43: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   26 |     void change(int v, int l, int r, int x){
      |                                           ^
regions.cpp:37:32: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   37 |     int get(int v, int l, int r){
      |                                ^
regions.cpp:63:26: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   63 | void dfs1(int v, int came){
      |                          ^
regions.cpp:71:24: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   71 | bool isAnc(int a, int b){
      |                        ^
regions.cpp:76:15: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   76 | void dfs(int v){
      |               ^
regions.cpp:95:18: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   95 | void calc(int ind){
      |                  ^
regions.cpp:106:25: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
  106 | long long f(int a, int b){
      |                         ^
regions.cpp:130:10: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
  130 | int main(){
      |          ^
# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 14396 KB Output is correct
2 Correct 13 ms 14408 KB Output is correct
3 Correct 14 ms 14452 KB Output is correct
4 Correct 18 ms 14408 KB Output is correct
5 Correct 30 ms 14408 KB Output is correct
6 Correct 49 ms 14532 KB Output is correct
7 Correct 69 ms 14528 KB Output is correct
8 Correct 85 ms 14684 KB Output is correct
9 Correct 135 ms 15040 KB Output is correct
10 Correct 242 ms 15296 KB Output is correct
11 Correct 437 ms 15584 KB Output is correct
12 Correct 550 ms 16500 KB Output is correct
13 Correct 965 ms 16312 KB Output is correct
14 Correct 1639 ms 16668 KB Output is correct
15 Correct 2065 ms 19192 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 5678 ms 21216 KB Output is correct
2 Correct 6446 ms 20680 KB Output is correct
3 Execution timed out 8038 ms 23688 KB Time limit exceeded
4 Correct 1583 ms 17344 KB Output is correct
5 Correct 1578 ms 19076 KB Output is correct
6 Correct 2249 ms 18784 KB Output is correct
7 Correct 1906 ms 19352 KB Output is correct
8 Execution timed out 8051 ms 25364 KB Time limit exceeded
9 Execution timed out 8073 ms 25976 KB Time limit exceeded
10 Execution timed out 8077 ms 29468 KB Time limit exceeded
11 Execution timed out 8073 ms 27240 KB Time limit exceeded
12 Execution timed out 8055 ms 28480 KB Time limit exceeded
13 Execution timed out 8061 ms 29348 KB Time limit exceeded
14 Execution timed out 8037 ms 34912 KB Time limit exceeded
15 Execution timed out 8022 ms 33416 KB Time limit exceeded
16 Execution timed out 8023 ms 41096 KB Time limit exceeded
17 Execution timed out 8042 ms 44720 KB Time limit exceeded