답안 #411593

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
411593 2021-05-25T14:51:17 Z AugustinasJucas Regions (IOI09_regions) C++14
4 / 100
3079 ms 64716 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);
    }
    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].l + tree[v*2+1].r;
        }
    }
    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[a]){
	    tree.change(1, enter[x], enter[x], 1);
    }
    for(auto x : regs[b]){
        ret += tree.get(1, enter[x], leave[x]);
    }
	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)-15;
	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:25:43: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   25 |     void change(int v, int l, int r, int x){
      |                                           ^
regions.cpp:36:32: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   36 |     int get(int v, int l, int r){
      |                                ^
regions.cpp:62:26: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   62 | void dfs1(int v, int came){
      |                          ^
regions.cpp:70:24: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   70 | bool isAnc(int a, int b){
      |                        ^
regions.cpp:75:15: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   75 | void dfs(int v){
      |               ^
regions.cpp:94:18: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   94 | void calc(int ind){
      |                  ^
regions.cpp:105:25: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
  105 | long long f(int a, int b){
      |                         ^
regions.cpp:126:10: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
  126 | int main(){
      |          ^
# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 14408 KB Output is correct
2 Correct 10 ms 14408 KB Output is correct
3 Correct 11 ms 14536 KB Output is correct
4 Correct 16 ms 14664 KB Output is correct
5 Incorrect 16 ms 14760 KB Output isn't correct
6 Incorrect 21 ms 14572 KB Output isn't correct
7 Incorrect 45 ms 14544 KB Output isn't correct
8 Incorrect 48 ms 14656 KB Output isn't correct
9 Incorrect 60 ms 15168 KB Output isn't correct
10 Incorrect 110 ms 15264 KB Output isn't correct
11 Incorrect 112 ms 15516 KB Output isn't correct
12 Incorrect 174 ms 16404 KB Output isn't correct
13 Incorrect 103 ms 16308 KB Output isn't correct
14 Incorrect 259 ms 17344 KB Output isn't correct
15 Incorrect 175 ms 20208 KB Output isn't correct
# 결과 실행 시간 메모리 Grader output
1 Incorrect 986 ms 20884 KB Output isn't correct
2 Incorrect 1213 ms 20792 KB Output isn't correct
3 Incorrect 1609 ms 24764 KB Output isn't correct
4 Incorrect 291 ms 19200 KB Output isn't correct
5 Incorrect 392 ms 18932 KB Output isn't correct
6 Incorrect 987 ms 26392 KB Output isn't correct
7 Incorrect 1090 ms 28128 KB Output isn't correct
8 Incorrect 1108 ms 42612 KB Output isn't correct
9 Incorrect 2115 ms 29056 KB Output isn't correct
10 Incorrect 2373 ms 64716 KB Output isn't correct
11 Incorrect 2784 ms 35236 KB Output isn't correct
12 Incorrect 1118 ms 28300 KB Output isn't correct
13 Incorrect 1724 ms 30424 KB Output isn't correct
14 Incorrect 2385 ms 36976 KB Output isn't correct
15 Incorrect 2635 ms 37044 KB Output isn't correct
16 Incorrect 2591 ms 44008 KB Output isn't correct
17 Incorrect 3079 ms 48996 KB Output isn't correct