oj.uz

Submission #283568

# Submission time Handle Problem Language Result Execution time Memory
283568 2020-08-26T01:44:28 Z sjimed Iqea (innopolis2018_final_C) C++14
20 / 100
 909 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;
int ans[100010];

struct T{
	int n;
	vector<int> g[100010];
	map<pii, int> m;
	int p[100010];
	int par[100010];
	int sum[100010];
	int d[100010];
	int sp[100010][21];
	bool chk[100010];
	int dis[100010][21];

	void mk(int k) {
		n = k;
		for(int i=1; i<=n; i++) {
			p[i] = i;
			d[i] = 0;
			sum[i] = 0;
			sp[i][0] = 0;
		}
	}

	int Find(int a) { return p[a] = p[a] == a ? a : Find(a); }
	void Union(int a, int b) { p[Find(b)] = Find(a); }

	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);
		}
	}

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

		dfs(Find(1));
		makeCen(Find(1), 0);

		for(int i=1; i<=n; i++) {
			if(i != Find(i)) continue;

			for(int j=0, k = i; k && j<=20; j++, k = par[k]) {
				dis[i][j] = dist(i, k);
			}
		}
	}
} t;

int main() {
	fast;

	int n;
	cin >> n;

	t.mk(n);

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

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

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

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

	t.init();

	int q;
	cin >> q;

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

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

		if(T == 1) {
			for(int i = k, j = 0; i; i = t.par[i], j++) {
				ans[i] = min(ans[i], t.dis[k][j]);
			}		
		}
		else {
			int ret = inf;
			for(int i = k, j = 0; i; i = t.par[i], j++) {
				ret = min(ret, ans[i] + t.dis[k][j]);
			}

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

Compilation message

C.cpp: In member function 'void T::makeCen(int, int)':
C.cpp:76:23: warning: 'mxi' may be used uninitialized in this function [-Wmaybe-uninitialized]
   76 |   int s = 1, mx = -1, mxi;
      |                       ^~~
C.cpp: In member function 'void T::init()':
C.cpp:76:23: warning: 'mxi' may be used uninitialized in this function [-Wmaybe-uninitialized]

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 554 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 554 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 842 ms 41020 KB Output is correct
2 Correct 804 ms 39672 KB Output is correct
3 Correct 795 ms 37368 KB Output is correct
4 Correct 798 ms 40184 KB Output is correct
5 Correct 834 ms 37324 KB Output is correct
6 Correct 794 ms 40056 KB Output is correct
7 Runtime error 726 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 665 ms 32796 KB Output is correct
2 Correct 751 ms 33064 KB Output is correct
3 Correct 647 ms 33112 KB Output is correct
4 Correct 693 ms 33528 KB Output is correct
5 Correct 597 ms 32964 KB Output is correct
6 Correct 622 ms 32888 KB Output is correct
7 Correct 677 ms 33456 KB Output is correct
8 Correct 641 ms 33172 KB Output is correct
9 Correct 655 ms 33168 KB Output is correct
10 Correct 773 ms 35960 KB Output is correct
11 Correct 748 ms 35704 KB Output is correct
12 Correct 882 ms 36672 KB Output is correct
13 Correct 771 ms 36028 KB Output is correct
14 Correct 670 ms 35576 KB Output is correct
15 Correct 825 ms 40660 KB Output is correct
16 Correct 699 ms 39676 KB Output is correct
17 Correct 868 ms 39488 KB Output is correct
18 Correct 745 ms 37112 KB Output is correct
19 Correct 885 ms 39680 KB Output is correct
20 Correct 843 ms 37752 KB Output is correct
21 Correct 842 ms 37264 KB Output is correct
22 Correct 818 ms 37840 KB Output is correct
23 Correct 875 ms 39728 KB Output is correct
24 Correct 861 ms 38264 KB Output is correct
25 Correct 882 ms 39780 KB Output is correct
26 Correct 867 ms 39456 KB Output is correct
27 Correct 902 ms 37052 KB Output is correct
28 Correct 909 ms 39700 KB Output is correct

Subtask #5
0 / 29.0

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