oj.uz

Submission #297061

# Submission time Handle Problem Language Result Execution time Memory
297061 2020-09-11T08:28:13 Z tmwilliamlin168 Swapping Cities (APIO20_swap) C++14
13 / 100
 605 ms 54436 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);
		adj2[u].clear();
	}
	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(find(f[1]), f[0]);
				adj[f[2]].push_back({f[0], f[1]});
				if(adj[f[2]].size()>2)
					dfs2(find(f[2]), f[0]);
			} else
				// g.push_back(f);
				dfs2(find(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
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11648 KB Output is correct
2 Correct 8 ms 11648 KB Output is correct
3 Correct 7 ms 11648 KB Output is correct
4 Correct 8 ms 11904 KB Output is correct
5 Correct 9 ms 12032 KB Output is correct
6 Correct 8 ms 12032 KB Output is correct
7 Correct 8 ms 12064 KB Output is correct
8 Correct 8 ms 12136 KB Output is correct
9 Correct 230 ms 38348 KB Output is correct
10 Correct 307 ms 45972 KB Output is correct
11 Correct 303 ms 44736 KB Output is correct
12 Correct 332 ms 47040 KB Output is correct
13 Correct 299 ms 49248 KB Output is correct
14 Correct 259 ms 37816 KB Output is correct
15 Correct 599 ms 47632 KB Output is correct
16 Correct 564 ms 45084 KB Output is correct
17 Correct 569 ms 51108 KB Output is correct
18 Correct 548 ms 49192 KB Output is correct
19 Correct 136 ms 21184 KB Output is correct
20 Correct 583 ms 52444 KB Output is correct
21 Correct 572 ms 50276 KB Output is correct
22 Correct 605 ms 54052 KB Output is correct
23 Correct 549 ms 54436 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11648 KB Output is correct
2 Correct 8 ms 11648 KB Output is correct
3 Correct 265 ms 43616 KB Output is correct
4 Correct 274 ms 48808 KB Output is correct
5 Correct 277 ms 48304 KB Output is correct
6 Correct 269 ms 48688 KB Output is correct
7 Correct 276 ms 48624 KB Output is correct
8 Correct 276 ms 47260 KB Output is correct
9 Correct 282 ms 48388 KB Output is correct
10 Correct 267 ms 47012 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 11648 KB Output is correct
2 Correct 7 ms 11648 KB Output is correct
3 Correct 8 ms 11648 KB Output is correct
4 Correct 7 ms 11648 KB Output is correct
5 Correct 8 ms 11904 KB Output is correct
6 Correct 9 ms 12032 KB Output is correct
7 Correct 8 ms 12032 KB Output is correct
8 Correct 8 ms 12064 KB Output is correct
9 Correct 8 ms 12136 KB Output is correct
10 Correct 9 ms 12032 KB Output is correct
11 Incorrect 9 ms 12064 KB Output isn't correct
12 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 7 ms 11648 KB Output is correct
3 Correct 8 ms 11648 KB Output is correct
4 Correct 7 ms 11648 KB Output is correct
5 Correct 8 ms 11904 KB Output is correct
6 Correct 9 ms 12032 KB Output is correct
7 Correct 8 ms 12032 KB Output is correct
8 Correct 8 ms 12064 KB Output is correct
9 Correct 8 ms 12136 KB Output is correct
10 Correct 230 ms 38348 KB Output is correct
11 Correct 307 ms 45972 KB Output is correct
12 Correct 303 ms 44736 KB Output is correct
13 Correct 332 ms 47040 KB Output is correct
14 Correct 299 ms 49248 KB Output is correct
15 Correct 9 ms 12032 KB Output is correct
16 Incorrect 9 ms 12064 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11648 KB Output is correct
2 Correct 8 ms 11648 KB Output is correct
3 Correct 7 ms 11648 KB Output is correct
4 Correct 8 ms 11904 KB Output is correct
5 Correct 9 ms 12032 KB Output is correct
6 Correct 8 ms 12032 KB Output is correct
7 Correct 8 ms 12064 KB Output is correct
8 Correct 8 ms 12136 KB Output is correct
9 Correct 230 ms 38348 KB Output is correct
10 Correct 307 ms 45972 KB Output is correct
11 Correct 303 ms 44736 KB Output is correct
12 Correct 332 ms 47040 KB Output is correct
13 Correct 299 ms 49248 KB Output is correct
14 Correct 259 ms 37816 KB Output is correct
15 Correct 599 ms 47632 KB Output is correct
16 Correct 564 ms 45084 KB Output is correct
17 Correct 569 ms 51108 KB Output is correct
18 Correct 548 ms 49192 KB Output is correct
19 Correct 265 ms 43616 KB Output is correct
20 Correct 274 ms 48808 KB Output is correct
21 Correct 277 ms 48304 KB Output is correct
22 Correct 269 ms 48688 KB Output is correct
23 Correct 276 ms 48624 KB Output is correct
24 Correct 276 ms 47260 KB Output is correct
25 Correct 282 ms 48388 KB Output is correct
26 Correct 267 ms 47012 KB Output is correct
27 Correct 9 ms 12032 KB Output is correct
28 Incorrect 9 ms 12064 KB Output isn't correct
29 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 7 ms 11648 KB Output is correct
3 Correct 8 ms 11648 KB Output is correct
4 Correct 7 ms 11648 KB Output is correct
5 Correct 8 ms 11904 KB Output is correct
6 Correct 9 ms 12032 KB Output is correct
7 Correct 8 ms 12032 KB Output is correct
8 Correct 8 ms 12064 KB Output is correct
9 Correct 8 ms 12136 KB Output is correct
10 Correct 230 ms 38348 KB Output is correct
11 Correct 307 ms 45972 KB Output is correct
12 Correct 303 ms 44736 KB Output is correct
13 Correct 332 ms 47040 KB Output is correct
14 Correct 299 ms 49248 KB Output is correct
15 Correct 259 ms 37816 KB Output is correct
16 Correct 599 ms 47632 KB Output is correct
17 Correct 564 ms 45084 KB Output is correct
18 Correct 569 ms 51108 KB Output is correct
19 Correct 548 ms 49192 KB Output is correct
20 Correct 265 ms 43616 KB Output is correct
21 Correct 274 ms 48808 KB Output is correct
22 Correct 277 ms 48304 KB Output is correct
23 Correct 269 ms 48688 KB Output is correct
24 Correct 276 ms 48624 KB Output is correct
25 Correct 276 ms 47260 KB Output is correct
26 Correct 282 ms 48388 KB Output is correct
27 Correct 267 ms 47012 KB Output is correct
28 Correct 9 ms 12032 KB Output is correct
29 Incorrect 9 ms 12064 KB Output isn't correct
30 Halted 0 ms 0 KB -