oj.uz

Submission #297054

# Submission time Handle Problem Language Result Execution time Memory
297054 2020-09-11T08:25:59 Z tmwilliamlin168 Swapping Cities (APIO20_swap) C++14
0 / 100
 589 ms 55332 KB 
#include "swap.h"
#include <bits/stdc++.h>
using namespace std;

#define ar array

const int mxN=1e5;
int n, a[mxN], r[mxN];

struct tree {
	int d[mxN], anc[mxN][17], anc2[mxN][17], b1[mxN][17], b2[mxN][17];
	vector<ar<int, 2>> adj[mxN];
	vector<int> adj2[mxN];
	int find(int x) {
		return x^r[x]?r[x]=find(r[x]):x;
	}
	bool join(int x, int y) {
		if((x=find(x))==(y=find(y)))
			return 0;
		r[x]=y;
		adj2[y].push_back(x);
		return 1;
	}
	void dfs2(int u, int w) {
		a[u]=min(w, a[u]);
		for(int v : adj2[u])
			dfs2(v, w);
	}
	vector<ar<int, 3>> co(vector<ar<int, 3>> e) {
		iota(r, r+n, 0);
		vector<ar<int, 3>> g;
		for(auto f : e) {
			if(join(f[1], f[2])) {
				adj[f[1]].push_back({f[0], f[2]});
				if(adj[f[1]].size()>2)
					dfs2(f[1], f[0]);
				adj[f[2]].push_back({f[0], f[1]});
				if(adj[f[2]].size()>2)
					dfs2(f[2], f[0]);
			} else
				// g.push_back(f);
				dfs2(f[1], f[0]);
		}
		memset(b2, 0x3f, sizeof(b2));
		return g;
	}
	int gv(int u, int x, int y) {
		int r=a[u];
		for(auto e : adj[u]) {
			if(e[1]^x&&e[1]^y) {
				r=min(e[0], r);
				break;
			}
		}
		return r;
	}
	void dfs(int u=0, int p=-1) {
		anc[u][0]=p;
		anc2[u][0]=u;
		for(int i=1; i<17; ++i) {
			anc[u][i]=~anc[u][i-1]?anc[anc[u][i-1]][i-1]:-1;
			anc2[u][i]=~anc[u][i-1]?anc2[anc[u][i-1]][i-1]:0;
			b1[u][i]=~anc[u][i-1]?max(b1[u][i-1], b1[anc[u][i-1]][i-1]):0;
		}
		if(u) {
			b2[u][1]=gv(p, u, anc[p][0]);
			for(int i=2; i<17; ++i)
				b2[u][2]=~anc[u][i-1]?min({b2[u][i-1], b2[anc[u][i-1]][i-1], gv(anc[u][i-1], anc2[u][i-1], anc[anc[u][i-1]][0])}):0;
		}
		for(auto v : adj[u]) {
			if(v[1]^p) {
				b1[v[1]][0]=v[0];
				d[v[1]]=d[u]+1;
				dfs(v[1], u);
			}
		}
	}
	int qry(int x, int y) {
		if(d[x]<d[y])
			swap(x, y);
		int r=0;
		for(int i=16; ~i; --i) {
			if(d[x]-(1<<i)>=d[y]) {
				r=max(b1[x][i], r);
				x=anc[x][i];
			}
		}
		if(x==y)
			return r;
		for(int i=16; ~i; --i) {
			if(anc[x][i]^anc[y][i]) {
				r=max({b1[x][i], b1[y][i], r});
				x=anc[x][i];
				y=anc[y][i];
			}
		}
		return max({b1[x][0], b1[y][0], r});
	}
	int qry2(int x, int y) {
		if(d[x]<d[y])
			swap(x, y);
		int r=2e9, x2=x, y2=y;
		for(int i=16; ~i; --i) {
			if(d[x]-(1<<i)>=d[y]) {
				if(x2^x)
					r=min(gv(x, x2, anc[x][0]), r);
				r=min(b2[x][i], r);
				x2=anc2[x][i];
				x=anc[x][i];
			}
		}
		if(x==y)
			return r;
		for(int i=16; ~i; --i) {
			if(anc[x][i]^anc[y][i]) {
				if(x2^x)
					r=min(gv(x, x2, anc[x][0]), r);
				if(y2^y)
					r=min(gv(y, y2, anc[y][0]), r);
				r=min({b2[x][i], b2[y][i], r});
				x2=anc2[x][i];
				y2=anc2[y][i];
				x=anc[x][i];
				y=anc[y][i];
			}
		}
		if(x2^x)
			r=min(gv(x, x2, anc[x][0]), r);
		if(y2^y)
			r=min(gv(y, y2, anc[y][0]), r);
		return min(gv(anc[x][0], x, y), r);
	}
} t0;//, t1;

void init(int n, int m, vector<int> u, vector<int> v, vector<int> w) {
	::n=n;
	vector<ar<int, 3>> e;
	for(int i=0; i<m; ++i)
		e.push_back({w[i], u[i], v[i]});
	sort(e.begin(), e.end());
	memset(a, 0x3f, 4*n);
	e=t0.co(e);
	/*t1.co(e);
	for(auto f : e) {
		a[f[1]]=max(f[0], a[f[1]]);
		a[f[2]]=max(f[0], a[f[2]]);
	}*/
	t0.dfs();
	//t1.dfs();
}

int getMinimumFuelCapacity(int x, int y) {
	// cout << t0.qry(x, y) << " " << t0.qry2(x, y) << " " << t1.qry(x, y) << endl;
	// int a=min(max(t0.qry(x, y), t0.qry2(x, y)), t1.qry(x, y));
	int b=max(t0.qry(x, y), a[x]);
	return b>1e9?-1:b;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 11648 KB Output is correct
2 Correct 8 ms 11648 KB Output is correct
3 Correct 8 ms 11648 KB Output is correct
4 Correct 9 ms 11936 KB Output is correct
5 Correct 9 ms 12032 KB Output is correct
6 Correct 9 ms 12032 KB Output is correct
7 Correct 9 ms 12032 KB Output is correct
8 Correct 9 ms 12160 KB Output is correct
9 Correct 244 ms 40028 KB Output is correct
10 Correct 328 ms 47896 KB Output is correct
11 Correct 306 ms 46816 KB Output is correct
12 Correct 345 ms 49344 KB Output is correct
13 Correct 307 ms 51264 KB Output is correct
14 Correct 260 ms 39480 KB Output is correct
15 Correct 589 ms 52072 KB Output is correct
16 Correct 570 ms 49140 KB Output is correct
17 Correct 571 ms 55332 KB Output is correct
18 Correct 546 ms 53672 KB Output is correct
19 Incorrect 127 ms 21948 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 11648 KB Output is correct
2 Correct 8 ms 11648 KB Output is correct
3 Incorrect 269 ms 46172 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 11648 KB Output is correct
2 Correct 8 ms 11648 KB Output is correct
3 Correct 8 ms 11648 KB Output is correct
4 Correct 8 ms 11648 KB Output is correct
5 Correct 9 ms 11936 KB Output is correct
6 Correct 9 ms 12032 KB Output is correct
7 Correct 9 ms 12032 KB Output is correct
8 Correct 9 ms 12032 KB Output is correct
9 Correct 9 ms 12160 KB Output is correct
10 Incorrect 9 ms 12032 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 11648 KB Output is correct
2 Correct 8 ms 11648 KB Output is correct
3 Correct 8 ms 11648 KB Output is correct
4 Correct 8 ms 11648 KB Output is correct
5 Correct 9 ms 11936 KB Output is correct
6 Correct 9 ms 12032 KB Output is correct
7 Correct 9 ms 12032 KB Output is correct
8 Correct 9 ms 12032 KB Output is correct
9 Correct 9 ms 12160 KB Output is correct
10 Correct 244 ms 40028 KB Output is correct
11 Correct 328 ms 47896 KB Output is correct
12 Correct 306 ms 46816 KB Output is correct
13 Correct 345 ms 49344 KB Output is correct
14 Correct 307 ms 51264 KB Output is correct
15 Incorrect 9 ms 12032 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 11648 KB Output is correct
2 Correct 8 ms 11648 KB Output is correct
3 Correct 8 ms 11648 KB Output is correct
4 Correct 9 ms 11936 KB Output is correct
5 Correct 9 ms 12032 KB Output is correct
6 Correct 9 ms 12032 KB Output is correct
7 Correct 9 ms 12032 KB Output is correct
8 Correct 9 ms 12160 KB Output is correct
9 Correct 244 ms 40028 KB Output is correct
10 Correct 328 ms 47896 KB Output is correct
11 Correct 306 ms 46816 KB Output is correct
12 Correct 345 ms 49344 KB Output is correct
13 Correct 307 ms 51264 KB Output is correct
14 Correct 260 ms 39480 KB Output is correct
15 Correct 589 ms 52072 KB Output is correct
16 Correct 570 ms 49140 KB Output is correct
17 Correct 571 ms 55332 KB Output is correct
18 Correct 546 ms 53672 KB Output is correct
19 Incorrect 269 ms 46172 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 11648 KB Output is correct
2 Correct 8 ms 11648 KB Output is correct
3 Correct 8 ms 11648 KB Output is correct
4 Correct 8 ms 11648 KB Output is correct
5 Correct 9 ms 11936 KB Output is correct
6 Correct 9 ms 12032 KB Output is correct
7 Correct 9 ms 12032 KB Output is correct
8 Correct 9 ms 12032 KB Output is correct
9 Correct 9 ms 12160 KB Output is correct
10 Correct 244 ms 40028 KB Output is correct
11 Correct 328 ms 47896 KB Output is correct
12 Correct 306 ms 46816 KB Output is correct
13 Correct 345 ms 49344 KB Output is correct
14 Correct 307 ms 51264 KB Output is correct
15 Correct 260 ms 39480 KB Output is correct
16 Correct 589 ms 52072 KB Output is correct
17 Correct 570 ms 49140 KB Output is correct
18 Correct 571 ms 55332 KB Output is correct
19 Correct 546 ms 53672 KB Output is correct
20 Incorrect 269 ms 46172 KB Output isn't correct
21 Halted 0 ms 0 KB -