oj.uz

Submission #282987

# Submission time Handle Problem Language Result Execution time Memory
282987 2020-08-25T08:13:54 Z 임성재(#5752) Iqea (innopolis2018_final_C) C++17
20 / 100
 830 ms 262148 KB 
#include<bits/stdc++.h>
using namespace std;

#define fast ios::sync_with_stdio(false); cin.tie(0);
#define fi first
#define se second
#define em emplace
#define eb emplace_back
#define mp make_pair
#define all(v) (v).begin(), (v).end()

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int inf = 1e9;
const ll INF = 1e18;

int n;
vector<int> g[100010];
map<pii, int> m;
int sum[100010];
int d[100010];
int sp[100010][21];
bool chk[100010];
int par[100010];
int ans[100010];

void dfs(int x) {
	for(int i=1; i<=20; i++) sp[x][i] = sp[sp[x][i-1]][i-1];

	sum[x] = 1;

	for(auto i : g[x]) {
		if(i == sp[x][0]) continue;

		sp[i][0] = x;
		d[i] = d[x] + 1;
		dfs(i);

		sum[x] += sum[i];
	}
}

int lca(int a, int b) {
	if(d[a] > d[b]) swap(a, b);

	for(int i=20; i>=0; i--) {
		if(d[b] - d[a] >= (1 << i)) b = sp[b][i];
	}

	if(a == b) return a;

	for(int i=20; i>=0; i--) {
		if(sp[a][i] != sp[b][i]) a = sp[a][i], b = sp[b][i];
	}

	return sp[a][0];
}

int dist(int a, int b) {
	return d[a] + d[b] - 2 * d[lca(a, b)];
}

int Cen(int x) {
	int s = 1, mx = -1, mxi;

	for(auto i : g[x]) {
		if(chk[i]) continue;

		s += sum[i];

		if(sum[i] > mx) {
			mx = sum[i];
			mxi = i;
		}
	}
	
	if(mx > s/2) {
		sum[x] = s - mx;
		return Cen(mxi);
	}

	return x;
}

void makeCen(int x, int p) {
	int c = Cen(x);
	par[c] = p;
	chk[c] = true;

	for(auto i : g[c]) {
		if(i == p || chk[i]) continue;

		makeCen(i, c);
	}
}

int main() {
	fast;

	cin >> n;

	for(int i=1; i<=n; i++) {
		int x, y;
		cin >> x >> y;

		ans[i] = inf;
		m[mp(x, y)] = i;
	}

	for(auto i : m) {
		int x = i.fi.fi;
		int y = i.fi.se;

		if(m.find(mp(x+1, y)) != m.end()) {
			int j = m[mp(x+1, y)];
			g[i.se].eb(j);
			g[j].eb(i.se);
		}
		if(m.find(mp(x-1, y)) != m.end()) {
			int j = m[mp(x-1, y)];
			g[i.se].eb(j);
			g[j].eb(i.se);
		}
		if(m.find(mp(x, y+1)) != m.end()) {
			int j = m[mp(x, y+1)];
			g[i.se].eb(j);
			g[j].eb(i.se);
		}
		if(m.find(mp(x, y-1)) != m.end()) {
			int j = m[mp(x, y-1)];
			g[i.se].eb(j);
			g[j].eb(i.se);
		}
	}

	for(int i=1; i<=n; i++) {
		sort(all(g[i]));
		g[i].erase(unique(all(g[i])), g[i].end());
	}

	dfs(1);

	makeCen(1, 0);

	int q;
	cin >> q;

	while(q--) {
		int t, x, y;
		cin >> t >> x >> y;

		int k = m[mp(x, y)];

		if(t == 1) {
			for(int i = k; i; i = par[i]) {
				ans[i] = min(ans[i], dist(i, k));
			}		
		}
		else {
			int ret = inf;
			for(int i=k; i; i = par[i]) {
				ret = min(ret, ans[i] + dist(i, k));
			}

			if(ret == inf) cout << "-1\n";
			else cout << ret << "\n";
		}
	}
}

Compilation message

C.cpp: In function 'int Cen(int)':
C.cpp:66:22: warning: 'mxi' may be used uninitialized in this function [-Wmaybe-uninitialized]
   66 |  int s = 1, mx = -1, mxi;
      |                      ^~~

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 607 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Runtime error 607 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 785 ms 31060 KB Output is correct
2 Correct 802 ms 29768 KB Output is correct
3 Correct 771 ms 28128 KB Output is correct
4 Correct 791 ms 30172 KB Output is correct
5 Correct 758 ms 27896 KB Output is correct
6 Correct 765 ms 30204 KB Output is correct
7 Runtime error 754 ms 262148 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 628 ms 24312 KB Output is correct
2 Correct 674 ms 24480 KB Output is correct
3 Correct 660 ms 24420 KB Output is correct
4 Correct 663 ms 24952 KB Output is correct
5 Correct 685 ms 24312 KB Output is correct
6 Correct 612 ms 24312 KB Output is correct
7 Correct 603 ms 24440 KB Output is correct
8 Correct 599 ms 24440 KB Output is correct
9 Correct 623 ms 24440 KB Output is correct
10 Correct 738 ms 27128 KB Output is correct
11 Correct 721 ms 26872 KB Output is correct
12 Correct 741 ms 27384 KB Output is correct
13 Correct 723 ms 27000 KB Output is correct
14 Correct 737 ms 26744 KB Output is correct
15 Correct 810 ms 30584 KB Output is correct
16 Correct 759 ms 29944 KB Output is correct
17 Correct 729 ms 29688 KB Output is correct
18 Correct 789 ms 27700 KB Output is correct
19 Correct 786 ms 29948 KB Output is correct
20 Correct 744 ms 28280 KB Output is correct
21 Correct 772 ms 27768 KB Output is correct
22 Correct 722 ms 28536 KB Output is correct
23 Correct 721 ms 29944 KB Output is correct
24 Correct 733 ms 28664 KB Output is correct
25 Correct 729 ms 29944 KB Output is correct
26 Correct 806 ms 29816 KB Output is correct
27 Correct 751 ms 28040 KB Output is correct
28 Correct 830 ms 30072 KB Output is correct

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Runtime error 607 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -