oj.uz

Submission #297079

# Submission time Handle Problem Language Result Execution time Memory
297079 2020-09-11T08:34:41 Z tmwilliamlin168 Swapping Cities (APIO20_swap) C++14
6 / 100
 2000 ms 50980 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 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 11904 KB Output is correct
5 Correct 9 ms 12024 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 229 ms 38456 KB Output is correct
10 Correct 305 ms 46104 KB Output is correct
11 Correct 308 ms 44860 KB Output is correct
12 Correct 330 ms 47168 KB Output is correct
13 Correct 281 ms 49216 KB Output is correct
14 Correct 263 ms 37812 KB Output is correct
15 Correct 580 ms 47760 KB Output is correct
16 Correct 578 ms 45176 KB Output is correct
17 Correct 572 ms 50980 KB Output is correct
18 Correct 541 ms 49444 KB Output is correct
19 Correct 131 ms 21184 KB Output is correct
20 Correct 587 ms 48268 KB Output is correct
21 Correct 576 ms 46232 KB Output is correct
22 Correct 606 ms 49828 KB Output is correct
23 Correct 561 ms 50596 KB Output is correct

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 Execution timed out 2076 ms 13420 KB Time limit exceeded
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 8 ms 11904 KB Output is correct
6 Correct 9 ms 12024 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 9 ms 12032 KB Output is correct
11 Incorrect 8 ms 12160 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 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 8 ms 11904 KB Output is correct
6 Correct 9 ms 12024 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 229 ms 38456 KB Output is correct
11 Correct 305 ms 46104 KB Output is correct
12 Correct 308 ms 44860 KB Output is correct
13 Correct 330 ms 47168 KB Output is correct
14 Correct 281 ms 49216 KB Output is correct
15 Correct 9 ms 12032 KB Output is correct
16 Incorrect 8 ms 12160 KB Output isn't correct
17 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 8 ms 11904 KB Output is correct
5 Correct 9 ms 12024 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 229 ms 38456 KB Output is correct
10 Correct 305 ms 46104 KB Output is correct
11 Correct 308 ms 44860 KB Output is correct
12 Correct 330 ms 47168 KB Output is correct
13 Correct 281 ms 49216 KB Output is correct
14 Correct 263 ms 37812 KB Output is correct
15 Correct 580 ms 47760 KB Output is correct
16 Correct 578 ms 45176 KB Output is correct
17 Correct 572 ms 50980 KB Output is correct
18 Correct 541 ms 49444 KB Output is correct
19 Execution timed out 2076 ms 13420 KB Time limit exceeded
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 8 ms 11904 KB Output is correct
6 Correct 9 ms 12024 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 229 ms 38456 KB Output is correct
11 Correct 305 ms 46104 KB Output is correct
12 Correct 308 ms 44860 KB Output is correct
13 Correct 330 ms 47168 KB Output is correct
14 Correct 281 ms 49216 KB Output is correct
15 Correct 263 ms 37812 KB Output is correct
16 Correct 580 ms 47760 KB Output is correct
17 Correct 578 ms 45176 KB Output is correct
18 Correct 572 ms 50980 KB Output is correct
19 Correct 541 ms 49444 KB Output is correct
20 Execution timed out 2076 ms 13420 KB Time limit exceeded
21 Halted 0 ms 0 KB -