oj.uz

Submission #410724

# Submission time Handle Problem Language Result Execution time Memory
410724 2021-05-23T12:48:14 Z songc Swapping Cities (APIO20_swap) C++14
17 / 100
 129 ms 38976 KB 
#include "swap.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define lb lower_bound
#define MOD 1000000007
#define INF (1ll<<62)
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;

struct Edge{int u, v, w;} E[202020];

int M, D[101010];
vector<pii> P[101010], C[101010];

int Pf(int u, int t){return P[u][lb(P[u].begin(), P[u].end(), pii(t+1, 0))-P[u].begin()-1].se;}
int Cf(int u, int t){return C[u][lb(C[u].begin(), C[u].end(), pii(t+1, 0))-C[u].begin()-1].se;}

int rt(int u, int t){
	if (Pf(u, t) < 0) return u;
	return rt(Pf(u, t), t);
}

void init(int N, int _M, vector<int> U, vector<int> V, vector<int> W) {
	M = _M;
	E[0].w = -1;
	for (int i=0; i<M; i++) E[i+1] = (Edge){U[i]+1, V[i]+1, W[i]};
	sort(E+1, E+M+1, [](Edge a, Edge b){return a.w < b.w;});
	for (int i=1; i<=N; i++) P[i].pb(pii(0, -i)), C[i].pb(pii(0, 0));
	for (int i=1; i<=M; i++){
		int ru = rt(E[i].u, i), rv = rt(E[i].v, i);
		if (ru != rv){
			if (Pf(ru, i) < Pf(rv, i)) swap(ru, rv);
			P[rv].pb(pii(i, Pf(ru, i)+Pf(rv, i)));
			P[ru].pb(pii(i, rv));
			if (Cf(ru, i) || Cf(rv, i)) C[rv].pb(pii(i, 1));
		}
		else C[rv].pb(pii(i, 1));
		D[E[i].u]++, D[E[i].v]++;
		if (D[E[i].u] > 2 || D[E[i].v] > 2) C[rv].pb(pii(i, 1));
	}
}

int getMinimumFuelCapacity(int X, int Y) {
	X++, Y++;
	int ans=0, lo=1, hi=M;
	while (lo<=hi){
		int m=lo+hi>>1;
		if (rt(X, m) == rt(Y, m) && Cf(rt(X, m), m)) ans=m, hi=m-1;
		else lo=m+1;
	}
	return E[ans].w;
}

Compilation message

swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
swap.cpp:50:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   50 |   int m=lo+hi>>1;
      |         ~~^~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 4 ms 5088 KB Output is correct
5 Correct 4 ms 5184 KB Output is correct
6 Correct 4 ms 5068 KB Output is correct
7 Correct 4 ms 5192 KB Output is correct
8 Correct 4 ms 5068 KB Output is correct
9 Runtime error 97 ms 29864 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Runtime error 129 ms 38976 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 4 ms 5088 KB Output is correct
5 Correct 4 ms 5184 KB Output is correct
6 Correct 4 ms 5068 KB Output is correct
7 Correct 4 ms 5192 KB Output is correct
8 Correct 4 ms 5068 KB Output is correct
9 Correct 4 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 4 ms 5188 KB Output is correct
13 Correct 4 ms 5060 KB Output is correct
14 Correct 4 ms 5060 KB Output is correct
15 Correct 4 ms 5196 KB Output is correct
16 Correct 4 ms 5068 KB Output is correct
17 Correct 4 ms 5196 KB Output is correct
18 Correct 4 ms 5196 KB Output is correct
19 Correct 4 ms 5068 KB Output is correct
20 Correct 5 ms 5112 KB Output is correct
21 Correct 4 ms 5196 KB Output is correct
22 Correct 6 ms 5196 KB Output is correct
23 Correct 4 ms 5068 KB Output is correct
24 Correct 5 ms 5176 KB Output is correct
25 Correct 5 ms 5196 KB Output is correct
26 Correct 5 ms 5160 KB Output is correct
27 Correct 4 ms 5156 KB Output is correct
28 Correct 5 ms 5188 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Correct 4 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 4 ms 5088 KB Output is correct
6 Correct 4 ms 5184 KB Output is correct
7 Correct 4 ms 5068 KB Output is correct
8 Correct 4 ms 5192 KB Output is correct
9 Correct 4 ms 5068 KB Output is correct
10 Runtime error 97 ms 29864 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 4 ms 5088 KB Output is correct
5 Correct 4 ms 5184 KB Output is correct
6 Correct 4 ms 5068 KB Output is correct
7 Correct 4 ms 5192 KB Output is correct
8 Correct 4 ms 5068 KB Output is correct
9 Runtime error 97 ms 29864 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Correct 4 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 4 ms 5088 KB Output is correct
6 Correct 4 ms 5184 KB Output is correct
7 Correct 4 ms 5068 KB Output is correct
8 Correct 4 ms 5192 KB Output is correct
9 Correct 4 ms 5068 KB Output is correct
10 Runtime error 97 ms 29864 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -