Submission #283568

#	Time	Username	Problem	Language	Result	Execution time	Memory
283568		sjimed	Iqea (innopolis2018_final_C)	C++14	20 / 100	909 ms	262148 KiB

C

#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 (stderr)

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
• Subtask 2: 0 / 19
• Subtask 3: 0 / 15
• Subtask 4: 20 / 20
• Subtask 5: 0 / 29