oj.uz

Submission #426883

# Submission time Handle Problem Language Result Execution time Memory
426883 2021-06-14T10:40:35 Z nots0fast Swapping Cities (APIO20_swap) C++17
13 / 100
 430 ms 36888 KB 
#include <bits/stdc++.h>
#include "swap.h"
using namespace std;
#define mp(a,b) make_pair(a,b)
#define ff first
#define setp(a) setprecision(a)<<fixed
#define ss second
#define fori(v) for(ll i=0; i<v; i++)
#define forj(v) for(ll j=0; j<v; j++)
#define fork(v) for(ll k=0; k<v; k++)
#define forl(v) for(ll l=0; l<v; l++)
#define fort(v) for(ll t=0; t<v; t++)
#define forz(v) for(ll z=0; z<v; z++)
#define forx(v) for(ll x=0; x<v; x++)
#define fory(v) for(ll y=0; y<v; y++)
#define ll long long
#define ld long double
#define pb(a) push_back(a)
const ll INF = 0x3f3f3f3f;
const ll inf = 1*pow(10,9) + 100;
ll modulo = pow(10,9) + 7;
#define MAX (int)(pow(10,5) + 10)


namespace dsu{
	int aid[MAX];
	vector<int> dsu[MAX];
	vector<pair<int,int> > nodeBelongs[MAX];	// nodes history of components
	int when[MAX];					// when did a component become 2 tracable
	int deg[MAX];					// degree of nodes
	
	
	void init(int n){
		fori(n)
			aid[i] = i, dsu[i].clear(), dsu[i].push_back(i), 
			when[i] = inf, deg[i] = 0, nodeBelongs[i].pb(mp(i, 0));
	}
	
	bool join(int a,int b, int w){  //	1 - if joined, 0 - if they were already joined 
		deg[a]++;
		deg[b]++;
		
		int aid1 = aid[a], aid2 = aid[b];
		
		if(deg[a] > 2){
			when[aid1] = min(when[aid1], w);
		}
		if(deg[b] > 2){
			when[aid2] = min(when[aid2], w);
		}
		
		if(dsu[aid2].size() > dsu[aid1].size())
			swap(aid1,aid2);
		
		if(aid1==aid2){
			when[aid1] = min(when[aid1], w);
			return 0;
		}
		
		when[aid1] = min(when[aid1], when[aid2]);
		for(auto hd : dsu[aid2]){
			aid[hd] = aid1;
			dsu[aid1].push_back(hd);
			nodeBelongs[hd].pb(mp(aid1, w));
		}
		dsu[aid2].clear();
		return 1;
	}
};


bool srt(vector<ll>& a, vector<ll>& b){
	return a[2] < b[2];
}



void init(int N, int M,	vector<int> U, vector<int> V, vector<int> W) {
	ll n = N, m = M;
	vector<vector<ll> > edges;
	fori(m){
		edges.pb(vector<ll>({U[i], V[i], W[i]}));
	}
	sort(edges.begin(), edges.end(), srt);
	
	dsu::init(n);
	
	for(auto& el : edges){
		dsu::join(el[0], el[1], el[2]);
	}
}


int getMinimumFuelCapacity(int X, int Y) {
	ll x = X, y = Y;
	if( (dsu::aid[x] != dsu::aid[y]) || (dsu::when[dsu::aid[x]] == inf)){
		return -1;
	}
	
	ll cmp1 = x, cmp2 = y;
	ll pt1 = 0, pt2 = 0;
	
	int ans = 0;
	while( (cmp1 != cmp2) || (dsu::when[cmp1] == inf) ){
		if(pt1 == (ll)dsu::nodeBelongs[x].size() ){
			cmp2 = dsu::nodeBelongs[y][pt2].ff;
			ans = max(ans, dsu::nodeBelongs[y][pt2].ss);
			++pt2;
		}
		else if(pt2 == (ll)dsu::nodeBelongs[y].size()){
			cmp1 =  dsu::nodeBelongs[x][pt1].ff;
			ans = max(ans, dsu::nodeBelongs[x][pt1].ss);
			++pt1;
		}
		else if(dsu::nodeBelongs[x][pt1].ss <= dsu::nodeBelongs[y][pt2].ss){
			cmp1 =  dsu::nodeBelongs[x][pt1].ff;
			ans = max(ans, dsu::nodeBelongs[x][pt1].ss);
			++pt1;
		}
		else{
			cmp2 = dsu::nodeBelongs[y][pt2].ff;
			ans = max(ans, dsu::nodeBelongs[y][pt2].ss);
			++pt2;
		}
	}
	
	ans = max(ans, dsu::when[cmp1]);
	
	return ans;
}

/*

void deal(){
	int n, m;
	cin>>n>>m;
	vector<int> u(m), v(m), w(m);
	fori(m){
		cin>>u[i];
	}
	fori(m){
		cin>>v[i];
	}
	fori(m){
		cin>>w[i];
	}
	
	init(n, m, u, v, w);
	ll q;
	cin>>q;
	forl(q){
		ll ui, vi;
		cin>>ui>>vi;
		cout<<getMinimumFuelCapacity(ui, vi)<<'\n';
	}
}



int main(){
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	deal();
}
*/

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 5004 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 5068 KB Output is correct
5 Correct 4 ms 5196 KB Output is correct
6 Correct 5 ms 5140 KB Output is correct
7 Correct 5 ms 5196 KB Output is correct
8 Correct 4 ms 5196 KB Output is correct
9 Correct 174 ms 27008 KB Output is correct
10 Correct 229 ms 31704 KB Output is correct
11 Correct 219 ms 31216 KB Output is correct
12 Correct 311 ms 32824 KB Output is correct
13 Correct 153 ms 25292 KB Output is correct
14 Correct 205 ms 27360 KB Output is correct
15 Correct 294 ms 36000 KB Output is correct
16 Correct 314 ms 35188 KB Output is correct
17 Correct 311 ms 36888 KB Output is correct
18 Correct 249 ms 29328 KB Output is correct
19 Correct 98 ms 13928 KB Output is correct
20 Correct 384 ms 35976 KB Output is correct
21 Correct 352 ms 34932 KB Output is correct
22 Correct 430 ms 36840 KB Output is correct
23 Correct 255 ms 29168 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 5004 KB Output is correct
3 Correct 262 ms 25584 KB Output is correct
4 Correct 234 ms 26436 KB Output is correct
5 Correct 271 ms 26032 KB Output is correct
6 Correct 255 ms 26364 KB Output is correct
7 Correct 247 ms 26356 KB Output is correct
8 Correct 230 ms 25436 KB Output is correct
9 Correct 269 ms 26136 KB Output is correct
10 Correct 258 ms 25324 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 5004 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 5068 KB Output is correct
5 Correct 4 ms 5196 KB Output is correct
6 Correct 5 ms 5140 KB Output is correct
7 Correct 5 ms 5196 KB Output is correct
8 Correct 4 ms 5196 KB Output is correct
9 Correct 3 ms 4940 KB Output is correct
10 Correct 4 ms 5196 KB Output is correct
11 Correct 4 ms 5196 KB Output is correct
12 Correct 5 ms 5196 KB Output is correct
13 Correct 5 ms 5136 KB Output is correct
14 Correct 4 ms 5144 KB Output is correct
15 Correct 5 ms 5144 KB Output is correct
16 Correct 4 ms 5196 KB Output is correct
17 Correct 4 ms 5212 KB Output is correct
18 Correct 5 ms 5156 KB Output is correct
19 Correct 4 ms 5068 KB Output is correct
20 Correct 6 ms 5196 KB Output is correct
21 Correct 5 ms 5196 KB Output is correct
22 Correct 5 ms 5196 KB Output is correct
23 Correct 4 ms 5068 KB Output is correct
24 Incorrect 5 ms 5324 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 5004 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 5068 KB Output is correct
6 Correct 4 ms 5196 KB Output is correct
7 Correct 5 ms 5140 KB Output is correct
8 Correct 5 ms 5196 KB Output is correct
9 Correct 4 ms 5196 KB Output is correct
10 Correct 174 ms 27008 KB Output is correct
11 Correct 229 ms 31704 KB Output is correct
12 Correct 219 ms 31216 KB Output is correct
13 Correct 311 ms 32824 KB Output is correct
14 Correct 153 ms 25292 KB Output is correct
15 Correct 4 ms 5196 KB Output is correct
16 Correct 4 ms 5196 KB Output is correct
17 Correct 5 ms 5196 KB Output is correct
18 Correct 5 ms 5136 KB Output is correct
19 Correct 4 ms 5144 KB Output is correct
20 Correct 5 ms 5144 KB Output is correct
21 Correct 4 ms 5196 KB Output is correct
22 Correct 4 ms 5212 KB Output is correct
23 Correct 5 ms 5156 KB Output is correct
24 Correct 4 ms 5068 KB Output is correct
25 Correct 6 ms 5196 KB Output is correct
26 Correct 5 ms 5196 KB Output is correct
27 Correct 5 ms 5196 KB Output is correct
28 Correct 4 ms 5068 KB Output is correct
29 Incorrect 5 ms 5324 KB Output isn't correct
30 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 5004 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 5068 KB Output is correct
5 Correct 4 ms 5196 KB Output is correct
6 Correct 5 ms 5140 KB Output is correct
7 Correct 5 ms 5196 KB Output is correct
8 Correct 4 ms 5196 KB Output is correct
9 Correct 174 ms 27008 KB Output is correct
10 Correct 229 ms 31704 KB Output is correct
11 Correct 219 ms 31216 KB Output is correct
12 Correct 311 ms 32824 KB Output is correct
13 Correct 153 ms 25292 KB Output is correct
14 Correct 205 ms 27360 KB Output is correct
15 Correct 294 ms 36000 KB Output is correct
16 Correct 314 ms 35188 KB Output is correct
17 Correct 311 ms 36888 KB Output is correct
18 Correct 249 ms 29328 KB Output is correct
19 Correct 262 ms 25584 KB Output is correct
20 Correct 234 ms 26436 KB Output is correct
21 Correct 271 ms 26032 KB Output is correct
22 Correct 255 ms 26364 KB Output is correct
23 Correct 247 ms 26356 KB Output is correct
24 Correct 230 ms 25436 KB Output is correct
25 Correct 269 ms 26136 KB Output is correct
26 Correct 258 ms 25324 KB Output is correct
27 Correct 4 ms 5196 KB Output is correct
28 Correct 4 ms 5196 KB Output is correct
29 Correct 5 ms 5196 KB Output is correct
30 Correct 5 ms 5136 KB Output is correct
31 Correct 4 ms 5144 KB Output is correct
32 Correct 5 ms 5144 KB Output is correct
33 Correct 4 ms 5196 KB Output is correct
34 Correct 4 ms 5212 KB Output is correct
35 Correct 5 ms 5156 KB Output is correct
36 Correct 23 ms 8264 KB Output is correct
37 Correct 281 ms 32436 KB Output is correct
38 Correct 252 ms 32144 KB Output is correct
39 Correct 262 ms 31808 KB Output is correct
40 Correct 267 ms 30708 KB Output is correct
41 Correct 269 ms 30336 KB Output is correct
42 Correct 201 ms 27852 KB Output is correct
43 Incorrect 268 ms 33000 KB Output isn't correct
44 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 5004 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 5068 KB Output is correct
6 Correct 4 ms 5196 KB Output is correct
7 Correct 5 ms 5140 KB Output is correct
8 Correct 5 ms 5196 KB Output is correct
9 Correct 4 ms 5196 KB Output is correct
10 Correct 174 ms 27008 KB Output is correct
11 Correct 229 ms 31704 KB Output is correct
12 Correct 219 ms 31216 KB Output is correct
13 Correct 311 ms 32824 KB Output is correct
14 Correct 153 ms 25292 KB Output is correct
15 Correct 205 ms 27360 KB Output is correct
16 Correct 294 ms 36000 KB Output is correct
17 Correct 314 ms 35188 KB Output is correct
18 Correct 311 ms 36888 KB Output is correct
19 Correct 249 ms 29328 KB Output is correct
20 Correct 262 ms 25584 KB Output is correct
21 Correct 234 ms 26436 KB Output is correct
22 Correct 271 ms 26032 KB Output is correct
23 Correct 255 ms 26364 KB Output is correct
24 Correct 247 ms 26356 KB Output is correct
25 Correct 230 ms 25436 KB Output is correct
26 Correct 269 ms 26136 KB Output is correct
27 Correct 258 ms 25324 KB Output is correct
28 Correct 4 ms 5196 KB Output is correct
29 Correct 4 ms 5196 KB Output is correct
30 Correct 5 ms 5196 KB Output is correct
31 Correct 5 ms 5136 KB Output is correct
32 Correct 4 ms 5144 KB Output is correct
33 Correct 5 ms 5144 KB Output is correct
34 Correct 4 ms 5196 KB Output is correct
35 Correct 4 ms 5212 KB Output is correct
36 Correct 5 ms 5156 KB Output is correct
37 Correct 23 ms 8264 KB Output is correct
38 Correct 281 ms 32436 KB Output is correct
39 Correct 252 ms 32144 KB Output is correct
40 Correct 262 ms 31808 KB Output is correct
41 Correct 267 ms 30708 KB Output is correct
42 Correct 269 ms 30336 KB Output is correct
43 Correct 201 ms 27852 KB Output is correct
44 Incorrect 268 ms 33000 KB Output isn't correct
45 Halted 0 ms 0 KB -