oj.uz

Submission #299803

# Submission time Handle Problem Language Result Execution time Memory
299803 2020-09-15T17:24:29 Z jacobtpl Swapping Cities (APIO20_swap) C++14
0 / 100
 2000 ms 23764 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 inside(int x,int a,int b) {
	return (x>=a && x<=b);
}
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 (inside(pre[ea],pre[a],bd[a]) && inside(pre[eb],pre[a],bd[a])) continue;
			if (!inside(pre[ea],pre[path[1]],bd[path[1]]) && !inside(pre[eb],pre[path[1]],bd[path[1]])) continue;
			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 (inside(pre[ea],pre[a],bd[a]) && inside(pre[eb],pre[a],bd[a])) continue;
			if (inside(pre[ea],pre[b],bd[b]) && inside(pre[eb],pre[b],bd[b])) continue;
			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 4992 KB Output is correct
4 Correct 5 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 158 ms 19412 KB Output is correct
10 Correct 233 ms 22264 KB Output is correct
11 Correct 246 ms 22460 KB Output is correct
12 Correct 273 ms 23764 KB Output is correct
13 Correct 177 ms 23632 KB Output is correct
14 Execution timed out 2063 ms 20432 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 2031 ms 23316 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 4992 KB Output is correct
5 Correct 5 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 5 ms 5248 KB Output is correct
11 Correct 5 ms 5248 KB Output is correct
12 Correct 5 ms 5248 KB Output is correct
13 Correct 4 ms 5120 KB Output is correct
14 Correct 5 ms 5248 KB Output is correct
15 Incorrect 5 ms 5248 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 4992 KB Output is correct
5 Correct 5 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 158 ms 19412 KB Output is correct
11 Correct 233 ms 22264 KB Output is correct
12 Correct 246 ms 22460 KB Output is correct
13 Correct 273 ms 23764 KB Output is correct
14 Correct 177 ms 23632 KB Output is correct
15 Correct 5 ms 5248 KB Output is correct
16 Correct 5 ms 5248 KB Output is correct
17 Correct 5 ms 5248 KB Output is correct
18 Correct 4 ms 5120 KB Output is correct
19 Correct 5 ms 5248 KB Output is correct
20 Incorrect 5 ms 5248 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 4992 KB Output is correct
4 Correct 5 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 158 ms 19412 KB Output is correct
10 Correct 233 ms 22264 KB Output is correct
11 Correct 246 ms 22460 KB Output is correct
12 Correct 273 ms 23764 KB Output is correct
13 Correct 177 ms 23632 KB Output is correct
14 Execution timed out 2063 ms 20432 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 4992 KB Output is correct
5 Correct 5 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 158 ms 19412 KB Output is correct
11 Correct 233 ms 22264 KB Output is correct
12 Correct 246 ms 22460 KB Output is correct
13 Correct 273 ms 23764 KB Output is correct
14 Correct 177 ms 23632 KB Output is correct
15 Execution timed out 2063 ms 20432 KB Time limit exceeded
16 Halted 0 ms 0 KB -