oj.uz

Submission #299805

# Submission time Handle Problem Language Result Execution time Memory
299805 2020-09-15T17:32:47 Z jacobtpl Swapping Cities (APIO20_swap) C++14
0 / 100
 2000 ms 21656 KB 
#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define INF 1100000000
#define sz(x) (int)(x).size()
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define ii pair<int,int>

int n,m;
vector<pair<int,ii> > e,ne;
struct ufds {
	vector<int> p;
	ufds(int n) {
		p.assign(n,0);
		for (int i=0;i<n;i++) p[i]=i;
	}
	int find(int x) {
		return (p[x]==x)?x:(p[x]=find(p[x]));
	}
	void join(int x,int y) {
		int a=find(x),b=find(y);
		if (a!=b) p[a]=b;
	}
	bool same(int x,int y) {
		return (find(x)==find(y));
	}
};

vector<ii> adj[100005],fadj[100005];
int p[100005],pre[100005],bd[100005],dp[100005],cur;
void form(int v,int d) {
	pre[v]=cur++;
	dp[v]=d;
	for (ii x:adj[v]) {
		if (x.first==p[v]) continue;
		p[x.first]=v;
		form(x.first,d+1);
	}
	bd[v]=cur-1;
}
void add_edge(int a,int b,int c) {
	adj[a].pb(mp(b,c));
	adj[b].pb(mp(a,c));
}
int dist[100005],pv[100005];
void dfs(int v,int d) {
	dist[v]=d;
	for (ii x:adj[v]) {
		if (dist[x.first]==INF) {
			pv[x.first]=v;
			dfs(x.first,max(d,x.second));
		}
	}
}
vector<int> path;
bool insub(int x,int v) {
	return (pre[x]>=pre[v] && pre[x]<=bd[v]);
}
vector<int> vec;
int shortest_path(int a,int b) {
	if (dp[a]<dp[b]) swap(a,b);
	pv[a]=-1;
	for (int i=0;i<n;i++) dist[i]=INF;
	dfs(a,0);
	int c=b;
	path.clear();
	while(c!=-1) {
		path.pb(c);
		c=pv[c];
	}
	int onpath=INF;
	for (int i=1;i<sz(path)-1;i++) {
		for (ii x:fadj[path[i]]) {
			if (x.first==path[i-1] || x.first==path[i+1]) continue;
			onpath=min(onpath,x.second);
		}
	}
	int ans=max(dist[b],onpath);

	vec.clear();
	for (ii x:fadj[a]) {
		if (x.first==path[sz(path)-2]) continue;
		vec.pb(x.second);
	}
	sort(all(vec));
	if (sz(vec)>=2) {
		ans=min(ans,max(dist[b],vec[1]));
	}

	vec.clear();
	for (ii x:fadj[b]) {
		if (x.first==path[1]) continue;
		vec.pb(x.second);
	}
	sort(all(vec));
	if (sz(vec)>=2) {
		ans=min(ans,max(dist[b],vec[1]));
	}

	if (p[path[1]]==b) {
		for (auto edge:ne) {
			int w=edge.first;
			int ea=edge.second.first;
			int eb=edge.second.second;
			if (insub(ea,a) && !insub(eb,path[1])) {
				ans=min(ans,max(dist[b],w));
				break;
			}
			if (insub(eb,a) && !insub(ea,path[1])) {
				ans=min(ans,max(dist[b],w));
				break;
			}
		}
	} else {
		for (auto edge:ne) {
			int w=edge.first;
			int ea=edge.second.first;
			int eb=edge.second.second;
			if (insub(ea,a) && insub(eb,b)) {
				ans=min(ans,max(dist[b],w));
				break;
			}
			if (insub(ea,b) && insub(eb,a)) {
				ans=min(ans,max(dist[b],w));
				break;
			}
		}
	}
	return ans;
}

void mst() {
	sort(all(e));
	ufds u(n);
	for (int i=0;i<m;i++) {
		int a=e[i].second.first,b=e[i].second.second;
		fadj[a].pb(mp(b,e[i].first));
		fadj[b].pb(mp(a,e[i].first));

		if (!u.same(a,b)) {
			u.join(a,b);
			add_edge(a,b,e[i].first);
			// printf("add %d %d to Tree\n", a,b);
		} else {
			ne.pb(e[i]);
		}
	}
	p[0]=-1;
	form(0,0);
}
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
	n=N;
	m=M;
	for (int i=0;i<m;i++) {
		e.pb(mp(W[i],mp(U[i],V[i])));
	}
	mst();
}

int getMinimumFuelCapacity(int x, int y) {
	int ans=shortest_path(x,y);

	if (ans>=INF) return -1;
	return ans;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4992 KB Output is correct
2 Correct 4 ms 4992 KB Output is correct
3 Correct 4 ms 5120 KB Output is correct
4 Correct 4 ms 5120 KB Output is correct
5 Correct 5 ms 5248 KB Output is correct
6 Correct 5 ms 5248 KB Output is correct
7 Correct 5 ms 5248 KB Output is correct
8 Correct 5 ms 5248 KB Output is correct
9 Correct 151 ms 17744 KB Output is correct
10 Correct 228 ms 20348 KB Output is correct
11 Correct 248 ms 20624 KB Output is correct
12 Correct 269 ms 21656 KB Output is correct
13 Correct 176 ms 21588 KB Output is correct
14 Execution timed out 2050 ms 18512 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4992 KB Output is correct
2 Correct 4 ms 4992 KB Output is correct
3 Execution timed out 2058 ms 19472 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4992 KB Output is correct
2 Correct 4 ms 4992 KB Output is correct
3 Correct 4 ms 4992 KB Output is correct
4 Correct 4 ms 5120 KB Output is correct
5 Correct 4 ms 5120 KB Output is correct
6 Correct 5 ms 5248 KB Output is correct
7 Correct 5 ms 5248 KB Output is correct
8 Correct 5 ms 5248 KB Output is correct
9 Correct 5 ms 5248 KB Output is correct
10 Correct 4 ms 5120 KB Output is correct
11 Correct 4 ms 5120 KB Output is correct
12 Correct 4 ms 5120 KB Output is correct
13 Correct 5 ms 5120 KB Output is correct
14 Correct 5 ms 5120 KB Output is correct
15 Incorrect 4 ms 5120 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4992 KB Output is correct
2 Correct 4 ms 4992 KB Output is correct
3 Correct 4 ms 4992 KB Output is correct
4 Correct 4 ms 5120 KB Output is correct
5 Correct 4 ms 5120 KB Output is correct
6 Correct 5 ms 5248 KB Output is correct
7 Correct 5 ms 5248 KB Output is correct
8 Correct 5 ms 5248 KB Output is correct
9 Correct 5 ms 5248 KB Output is correct
10 Correct 151 ms 17744 KB Output is correct
11 Correct 228 ms 20348 KB Output is correct
12 Correct 248 ms 20624 KB Output is correct
13 Correct 269 ms 21656 KB Output is correct
14 Correct 176 ms 21588 KB Output is correct
15 Correct 4 ms 5120 KB Output is correct
16 Correct 4 ms 5120 KB Output is correct
17 Correct 4 ms 5120 KB Output is correct
18 Correct 5 ms 5120 KB Output is correct
19 Correct 5 ms 5120 KB Output is correct
20 Incorrect 4 ms 5120 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4992 KB Output is correct
2 Correct 4 ms 4992 KB Output is correct
3 Correct 4 ms 5120 KB Output is correct
4 Correct 4 ms 5120 KB Output is correct
5 Correct 5 ms 5248 KB Output is correct
6 Correct 5 ms 5248 KB Output is correct
7 Correct 5 ms 5248 KB Output is correct
8 Correct 5 ms 5248 KB Output is correct
9 Correct 151 ms 17744 KB Output is correct
10 Correct 228 ms 20348 KB Output is correct
11 Correct 248 ms 20624 KB Output is correct
12 Correct 269 ms 21656 KB Output is correct
13 Correct 176 ms 21588 KB Output is correct
14 Execution timed out 2050 ms 18512 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4992 KB Output is correct
2 Correct 4 ms 4992 KB Output is correct
3 Correct 4 ms 4992 KB Output is correct
4 Correct 4 ms 5120 KB Output is correct
5 Correct 4 ms 5120 KB Output is correct
6 Correct 5 ms 5248 KB Output is correct
7 Correct 5 ms 5248 KB Output is correct
8 Correct 5 ms 5248 KB Output is correct
9 Correct 5 ms 5248 KB Output is correct
10 Correct 151 ms 17744 KB Output is correct
11 Correct 228 ms 20348 KB Output is correct
12 Correct 248 ms 20624 KB Output is correct
13 Correct 269 ms 21656 KB Output is correct
14 Correct 176 ms 21588 KB Output is correct
15 Execution timed out 2050 ms 18512 KB Time limit exceeded
16 Halted 0 ms 0 KB -