Submission #283617

#	Time	Username	Problem	Language	Result	Execution time	Memory
283617		sjimed	Iqea (innopolis2018_final_C)	C++14	36 / 100	2086 ms	97188 KiB

C

#include<bits/stdc++.h>
#include <unordered_map>
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;
unordered_map<int, int> ans;

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];

	int Find(int a) { return p[a] = p[a] == a ? a : Find(p[a]); }
	void Union(int a, int b) { if(Find(a) != Find(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() {
		n = m.size();

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

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

			if(m.find(mp(x, y+1)) != m.end()) Union(m[mp(x, y+1)], i.se);
			if(m.find(mp(x, y-1)) != m.end()) Union(m[mp(x, y-1)], i.se);
		}

		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[Find(j)].eb(Find(i.se));
			}
			if(m.find(mp(x-1, y)) != m.end()) {
				int j = m[mp(x-1, y)];
				g[Find(j)].eb(Find(i.se));
			}
		}

		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);
			}
		}
	}
} X, Y;

int main() {
	fast;

	int n;
	cin >> n;

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

		X.m[mp(x, y)] = i;
		Y.m[mp(y, x)] = i;
	}	

	X.init();
	Y.init();

	int q;
	cin >> q;

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

		int u = X.Find(X.m[mp(x, y)]);
		int v = Y.Find(Y.m[mp(y, x)]);

		if(T == 1) {
			for(int i = u, c1 = 0; i; i = X.par[i], c1++) {
				for(int j = v, c2 = 0; j; j = Y.par[j], c2++) {
					ans[n * i + j] = min(ans[n * i + j], X.dis[u][c1] + Y.dis[v][c2] - inf);
				}
			}
		}
		else {
			int ret = inf;
			for(int i = u, c1 = 0; i; i = X.par[i], c1++) {
				for(int j = v, c2 = 0; j; j = Y.par[j], c2++) {
					ret = min(ret, ans[n * i + j] + X.dis[u][c1] + Y.dis[v][c2] + inf);
				}
			}

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

• Subtask 1: 17 / 17
• Subtask 2: 19 / 19
• Subtask 3: 0 / 15
• Subtask 4: 0 / 20
• Subtask 5: 0 / 29