oj.uz

Submission #297085

# Submission time Handle Problem Language Result Execution time Memory
297085 2020-09-11T08:39:30 Z tmwilliamlin168 Swapping Cities (APIO20_swap) C++14
6 / 100
 2000 ms 47012 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];
	int find(int x) {
		return x^r[x]?r[x]=find(r[x]):x;
		// return 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, int p=-1) {
		/*
		a[u]=min(w, a[u]);
		for(int v : adj2[u])
			dfs2(v, w);
		// adj2[u].clear();
		*/
		a[u]=min(w, a[u]);
		for(auto v : adj[u])
			if(v[1]^p)
				dfs2(v[1], w, u);
	}
	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]});
				adj[f[2]].push_back({f[0], f[1]});
				if(adj[f[1]].size()>2||adj[f[2]].size()>2)
					dfs2(f[1], 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
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9344 KB Output is correct
2 Correct 6 ms 9344 KB Output is correct
3 Correct 6 ms 9344 KB Output is correct
4 Correct 7 ms 9472 KB Output is correct
5 Correct 8 ms 9600 KB Output is correct
6 Correct 7 ms 9600 KB Output is correct
7 Correct 7 ms 9728 KB Output is correct
8 Correct 7 ms 9728 KB Output is correct
9 Correct 226 ms 34960 KB Output is correct
10 Correct 288 ms 42136 KB Output is correct
11 Correct 273 ms 40896 KB Output is correct
12 Correct 296 ms 43072 KB Output is correct
13 Correct 274 ms 45264 KB Output is correct
14 Correct 240 ms 33976 KB Output is correct
15 Correct 561 ms 43664 KB Output is correct
16 Correct 565 ms 40948 KB Output is correct
17 Correct 538 ms 47012 KB Output is correct
18 Correct 504 ms 45348 KB Output is correct
19 Correct 126 ms 18496 KB Output is correct
20 Correct 541 ms 44404 KB Output is correct
21 Correct 563 ms 43288 KB Output is correct
22 Correct 583 ms 45604 KB Output is correct
23 Correct 529 ms 46116 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9344 KB Output is correct
2 Correct 6 ms 9344 KB Output is correct
3 Execution timed out 2062 ms 10412 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9344 KB Output is correct
2 Correct 7 ms 9344 KB Output is correct
3 Correct 6 ms 9344 KB Output is correct
4 Correct 6 ms 9344 KB Output is correct
5 Correct 7 ms 9472 KB Output is correct
6 Correct 8 ms 9600 KB Output is correct
7 Correct 7 ms 9600 KB Output is correct
8 Correct 7 ms 9728 KB Output is correct
9 Correct 7 ms 9728 KB Output is correct
10 Correct 9 ms 9600 KB Output is correct
11 Incorrect 8 ms 9728 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9344 KB Output is correct
2 Correct 7 ms 9344 KB Output is correct
3 Correct 6 ms 9344 KB Output is correct
4 Correct 6 ms 9344 KB Output is correct
5 Correct 7 ms 9472 KB Output is correct
6 Correct 8 ms 9600 KB Output is correct
7 Correct 7 ms 9600 KB Output is correct
8 Correct 7 ms 9728 KB Output is correct
9 Correct 7 ms 9728 KB Output is correct
10 Correct 226 ms 34960 KB Output is correct
11 Correct 288 ms 42136 KB Output is correct
12 Correct 273 ms 40896 KB Output is correct
13 Correct 296 ms 43072 KB Output is correct
14 Correct 274 ms 45264 KB Output is correct
15 Correct 9 ms 9600 KB Output is correct
16 Incorrect 8 ms 9728 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 9344 KB Output is correct
2 Correct 6 ms 9344 KB Output is correct
3 Correct 6 ms 9344 KB Output is correct
4 Correct 7 ms 9472 KB Output is correct
5 Correct 8 ms 9600 KB Output is correct
6 Correct 7 ms 9600 KB Output is correct
7 Correct 7 ms 9728 KB Output is correct
8 Correct 7 ms 9728 KB Output is correct
9 Correct 226 ms 34960 KB Output is correct
10 Correct 288 ms 42136 KB Output is correct
11 Correct 273 ms 40896 KB Output is correct
12 Correct 296 ms 43072 KB Output is correct
13 Correct 274 ms 45264 KB Output is correct
14 Correct 240 ms 33976 KB Output is correct
15 Correct 561 ms 43664 KB Output is correct
16 Correct 565 ms 40948 KB Output is correct
17 Correct 538 ms 47012 KB Output is correct
18 Correct 504 ms 45348 KB Output is correct
19 Execution timed out 2062 ms 10412 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9344 KB Output is correct
2 Correct 7 ms 9344 KB Output is correct
3 Correct 6 ms 9344 KB Output is correct
4 Correct 6 ms 9344 KB Output is correct
5 Correct 7 ms 9472 KB Output is correct
6 Correct 8 ms 9600 KB Output is correct
7 Correct 7 ms 9600 KB Output is correct
8 Correct 7 ms 9728 KB Output is correct
9 Correct 7 ms 9728 KB Output is correct
10 Correct 226 ms 34960 KB Output is correct
11 Correct 288 ms 42136 KB Output is correct
12 Correct 273 ms 40896 KB Output is correct
13 Correct 296 ms 43072 KB Output is correct
14 Correct 274 ms 45264 KB Output is correct
15 Correct 240 ms 33976 KB Output is correct
16 Correct 561 ms 43664 KB Output is correct
17 Correct 565 ms 40948 KB Output is correct
18 Correct 538 ms 47012 KB Output is correct
19 Correct 504 ms 45348 KB Output is correct
20 Execution timed out 2062 ms 10412 KB Time limit exceeded
21 Halted 0 ms 0 KB -