답안 #346726

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
346726 2021-01-10T19:50:36 Z AmineWeslati 자매 도시 (APIO20_swap) C++14
100 / 100
517 ms 82524 KB
//Never stop trying
/*#pragma GCC target ("avx2")
#pragma GCC optimize ("Ofast")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")*/
#include "bits/stdc++.h"
#ifndef LOCAL
#include "swap.h"
#endif

using namespace std;
#define boost ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
typedef string str;
typedef double db;
typedef long double ld;
typedef pair<int, int> pi;
#define fi first
#define se second
typedef vector<int> vi;
typedef vector<pi> vpi;
typedef vector<str> vs;
typedef vector<ld> vd;
#define pb push_back
#define eb emplace_back
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define endl "\n"

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)

const int MOD = 1e9 + 7; //998244353
const ll INF = 2e9+10;
const int MX = 3e5 + 10;
const int nx[4] = {0, 0, 1, -1}, ny[4] = {1, -1, 0, 0}; //right left down up

template<class T> using V = vector<T>;
template<class T> bool ckmin(T& a, const T& b) { return a > b ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

ll cdiv(ll a, ll b) { return a / b + ((a ^ b) > 0 && a % b); } // divide a by b rounded up
//constexpr int log2(int x) { return 31 - __builtin_clz(x); } // floor(log2(x))

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
//mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());

ll random(ll a, ll b){
    return a + rng() % (b - a + 1);
}

#ifndef LOCAL  
#define cerr if(false) cerr
#endif
#define dbg(x) cerr << #x << " : " << x << endl; 
#define dbgs(x,y) cerr << #x << " : " << x << " / " << #y << " : " << y << endl;
#define dbgv(v) cerr << #v << " : " << "[ "; for(auto it : v) cerr << it << ' '; cerr << ']' << endl;
#define here() cerr << "here" << endl;

void IO() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
}

#define left lft
#define right rgt

const int LOG=23;
int N;
vi parent(MX,-1), left(MX,-1), right(MX,-1), weight(MX,INF);

vi p(MX),can(MX,0),deg(MX,0);

int findSet(int u){ return p[u]==u ? u : p[u]=findSet(p[u]); }
void join(int u, int v, int nw){
	deg[u]++; deg[v]++;
	bool three=(deg[u]>=3 || deg[v]>=3);
	u=findSet(u); v=findSet(v);
	p[v]=p[u]=nw;
	if(u==v || three) can[nw]=1;
	can[nw]|=can[u];
	can[nw]|=can[v];
}

int jump[MX][LOG],jumpMin[MX][LOG],in[MX],out[MX],counter=0;
void euler(int u, int p){
	in[u]=++counter;
	jump[u][0]=p;
	jumpMin[u][0]=min(weight[u],weight[p]);
	FOR(i,1,LOG){
		jump[u][i]=jump[jump[u][i-1]][i-1];
		jumpMin[u][i]=min(jumpMin[u][i-1],jumpMin[jump[u][i-1]][i-1]);
	}
	if(left[u]!=-1) euler(left[u],u);
	if(left[u]!=right[u]) euler(right[u],u);
	out[u]=++counter;
}
bool ancestor(int u, int v){ return in[u]<=in[v] && out[u]>=out[v]; }
int LCA(int u, int v){
	if(ancestor(u,v)) return u;
	if(ancestor(v,u)) return v;
	ROF(i,0,LOG) if(!ancestor(jump[u][i],v)) u=jump[u][i];
	return jump[u][0];
}
int solve(int u){
	ROF(i,0,LOG) if(jumpMin[u][i]==INF) u=jump[u][i];
	return jumpMin[u][0];
}

int cnt;
void init(int N, int M, vi U, vi V, vi W){
	::N=N;
	vpi vec;
	FOR(i,0,M){
		vec.eb(W[i],i);
	}
	sort(all(vec));

	cnt=N-1;
	FOR(i,0,N+M) p[i]=i;
	for(auto x: vec){
		int i=x.se,w=x.fi,u=U[i],v=V[i];
		cnt++;

		parent[findSet(u)]=parent[findSet(v)]=cnt;
		left[cnt]=findSet(u),right[cnt]=findSet(v);
		join(u,v,cnt);

		if(can[findSet(u)]) weight[cnt]=w;
	}
	euler(cnt,cnt);
}

int getMinimumFuelCapacity(int u, int v) {
	int lca=LCA(u,v);
	int ans=solve(lca);
	if(ans>=INF) ans=-1;
	return ans;
}


#ifdef LOCAL
int main() {
	boost; IO();

	int N,M; cin>>N>>M;
	vi v(M),u(M),w(M);
	FOR(i,0,M) cin>>u[i];
	FOR(i,0,M) cin>>v[i];
	FOR(i,0,M) cin>>w[i];
	init(N,M,u,v,w);
	int a,b; cin>>a>>b;
	cout << getMinimumFuelCapacity(a,b) << endl;

	return 0;
}
#endif

/*
5 6
0 0 1 1 1 2
1 2 2 3 4 3
4 4 1 2 10 3
*/

/* Careful!!!
    .Array bounds
    .Infinite loops
    .Uninitialized variables / empty containers
    .Multisets are shit

   Some insights:
    .Binary search
    .Graph representation
    .Write brute force code
    .Change your approach
*/
# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 8556 KB Output is correct
2 Correct 6 ms 8556 KB Output is correct
3 Correct 6 ms 8556 KB Output is correct
4 Correct 6 ms 8684 KB Output is correct
5 Correct 6 ms 8940 KB Output is correct
6 Correct 6 ms 8940 KB Output is correct
7 Correct 6 ms 8940 KB Output is correct
8 Correct 6 ms 8940 KB Output is correct
9 Correct 115 ms 40672 KB Output is correct
10 Correct 144 ms 47712 KB Output is correct
11 Correct 139 ms 47072 KB Output is correct
12 Correct 150 ms 49376 KB Output is correct
13 Correct 178 ms 50912 KB Output is correct
14 Correct 129 ms 40672 KB Output is correct
15 Correct 286 ms 49632 KB Output is correct
16 Correct 282 ms 53108 KB Output is correct
17 Correct 295 ms 55392 KB Output is correct
18 Correct 409 ms 56928 KB Output is correct
19 Correct 124 ms 20588 KB Output is correct
20 Correct 279 ms 54944 KB Output is correct
21 Correct 273 ms 53308 KB Output is correct
22 Correct 289 ms 56188 KB Output is correct
23 Correct 445 ms 57648 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 8556 KB Output is correct
2 Correct 6 ms 8556 KB Output is correct
3 Correct 401 ms 52504 KB Output is correct
4 Correct 407 ms 58288 KB Output is correct
5 Correct 428 ms 57088 KB Output is correct
6 Correct 410 ms 58372 KB Output is correct
7 Correct 426 ms 57692 KB Output is correct
8 Correct 417 ms 55980 KB Output is correct
9 Correct 406 ms 57308 KB Output is correct
10 Correct 410 ms 55488 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 8556 KB Output is correct
2 Correct 6 ms 8556 KB Output is correct
3 Correct 6 ms 8556 KB Output is correct
4 Correct 6 ms 8556 KB Output is correct
5 Correct 6 ms 8684 KB Output is correct
6 Correct 6 ms 8940 KB Output is correct
7 Correct 6 ms 8940 KB Output is correct
8 Correct 6 ms 8940 KB Output is correct
9 Correct 6 ms 8940 KB Output is correct
10 Correct 6 ms 8940 KB Output is correct
11 Correct 7 ms 8940 KB Output is correct
12 Correct 7 ms 8940 KB Output is correct
13 Correct 7 ms 8940 KB Output is correct
14 Correct 7 ms 8940 KB Output is correct
15 Correct 7 ms 8940 KB Output is correct
16 Correct 7 ms 8940 KB Output is correct
17 Correct 7 ms 8940 KB Output is correct
18 Correct 7 ms 8940 KB Output is correct
19 Correct 7 ms 8940 KB Output is correct
20 Correct 7 ms 8940 KB Output is correct
21 Correct 7 ms 9068 KB Output is correct
22 Correct 7 ms 9068 KB Output is correct
23 Correct 7 ms 8940 KB Output is correct
24 Correct 7 ms 9196 KB Output is correct
25 Correct 7 ms 9196 KB Output is correct
26 Correct 8 ms 9324 KB Output is correct
27 Correct 7 ms 9068 KB Output is correct
28 Correct 7 ms 9196 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 8556 KB Output is correct
2 Correct 6 ms 8556 KB Output is correct
3 Correct 6 ms 8556 KB Output is correct
4 Correct 6 ms 8556 KB Output is correct
5 Correct 6 ms 8684 KB Output is correct
6 Correct 6 ms 8940 KB Output is correct
7 Correct 6 ms 8940 KB Output is correct
8 Correct 6 ms 8940 KB Output is correct
9 Correct 6 ms 8940 KB Output is correct
10 Correct 115 ms 40672 KB Output is correct
11 Correct 144 ms 47712 KB Output is correct
12 Correct 139 ms 47072 KB Output is correct
13 Correct 150 ms 49376 KB Output is correct
14 Correct 178 ms 50912 KB Output is correct
15 Correct 6 ms 8940 KB Output is correct
16 Correct 7 ms 8940 KB Output is correct
17 Correct 7 ms 8940 KB Output is correct
18 Correct 7 ms 8940 KB Output is correct
19 Correct 7 ms 8940 KB Output is correct
20 Correct 7 ms 8940 KB Output is correct
21 Correct 7 ms 8940 KB Output is correct
22 Correct 7 ms 8940 KB Output is correct
23 Correct 7 ms 8940 KB Output is correct
24 Correct 21 ms 14572 KB Output is correct
25 Correct 152 ms 51316 KB Output is correct
26 Correct 146 ms 51168 KB Output is correct
27 Correct 144 ms 51188 KB Output is correct
28 Correct 144 ms 50656 KB Output is correct
29 Correct 151 ms 50400 KB Output is correct
30 Correct 135 ms 46944 KB Output is correct
31 Correct 150 ms 51552 KB Output is correct
32 Correct 147 ms 51296 KB Output is correct
33 Correct 178 ms 53344 KB Output is correct
34 Correct 154 ms 51552 KB Output is correct
35 Correct 7 ms 8940 KB Output is correct
36 Correct 7 ms 8940 KB Output is correct
37 Correct 7 ms 9068 KB Output is correct
38 Correct 7 ms 9068 KB Output is correct
39 Correct 7 ms 8940 KB Output is correct
40 Correct 7 ms 9196 KB Output is correct
41 Correct 7 ms 9196 KB Output is correct
42 Correct 8 ms 9324 KB Output is correct
43 Correct 7 ms 9068 KB Output is correct
44 Correct 7 ms 9196 KB Output is correct
45 Correct 219 ms 61660 KB Output is correct
46 Correct 148 ms 51168 KB Output is correct
47 Correct 150 ms 51296 KB Output is correct
48 Correct 180 ms 54632 KB Output is correct
49 Correct 154 ms 51164 KB Output is correct
50 Correct 128 ms 42464 KB Output is correct
51 Correct 186 ms 54112 KB Output is correct
52 Correct 223 ms 68316 KB Output is correct
53 Correct 257 ms 72284 KB Output is correct
54 Correct 262 ms 78428 KB Output is correct
55 Correct 172 ms 53216 KB Output is correct
56 Correct 260 ms 72028 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 8556 KB Output is correct
2 Correct 6 ms 8556 KB Output is correct
3 Correct 6 ms 8556 KB Output is correct
4 Correct 6 ms 8684 KB Output is correct
5 Correct 6 ms 8940 KB Output is correct
6 Correct 6 ms 8940 KB Output is correct
7 Correct 6 ms 8940 KB Output is correct
8 Correct 6 ms 8940 KB Output is correct
9 Correct 115 ms 40672 KB Output is correct
10 Correct 144 ms 47712 KB Output is correct
11 Correct 139 ms 47072 KB Output is correct
12 Correct 150 ms 49376 KB Output is correct
13 Correct 178 ms 50912 KB Output is correct
14 Correct 129 ms 40672 KB Output is correct
15 Correct 286 ms 49632 KB Output is correct
16 Correct 282 ms 53108 KB Output is correct
17 Correct 295 ms 55392 KB Output is correct
18 Correct 409 ms 56928 KB Output is correct
19 Correct 401 ms 52504 KB Output is correct
20 Correct 407 ms 58288 KB Output is correct
21 Correct 428 ms 57088 KB Output is correct
22 Correct 410 ms 58372 KB Output is correct
23 Correct 426 ms 57692 KB Output is correct
24 Correct 417 ms 55980 KB Output is correct
25 Correct 406 ms 57308 KB Output is correct
26 Correct 410 ms 55488 KB Output is correct
27 Correct 6 ms 8940 KB Output is correct
28 Correct 7 ms 8940 KB Output is correct
29 Correct 7 ms 8940 KB Output is correct
30 Correct 7 ms 8940 KB Output is correct
31 Correct 7 ms 8940 KB Output is correct
32 Correct 7 ms 8940 KB Output is correct
33 Correct 7 ms 8940 KB Output is correct
34 Correct 7 ms 8940 KB Output is correct
35 Correct 7 ms 8940 KB Output is correct
36 Correct 21 ms 14572 KB Output is correct
37 Correct 152 ms 51316 KB Output is correct
38 Correct 146 ms 51168 KB Output is correct
39 Correct 144 ms 51188 KB Output is correct
40 Correct 144 ms 50656 KB Output is correct
41 Correct 151 ms 50400 KB Output is correct
42 Correct 135 ms 46944 KB Output is correct
43 Correct 150 ms 51552 KB Output is correct
44 Correct 147 ms 51296 KB Output is correct
45 Correct 178 ms 53344 KB Output is correct
46 Correct 154 ms 51552 KB Output is correct
47 Correct 34 ms 14472 KB Output is correct
48 Correct 289 ms 55192 KB Output is correct
49 Correct 284 ms 55216 KB Output is correct
50 Correct 285 ms 55092 KB Output is correct
51 Correct 287 ms 54852 KB Output is correct
52 Correct 274 ms 52524 KB Output is correct
53 Correct 246 ms 42344 KB Output is correct
54 Correct 283 ms 56112 KB Output is correct
55 Correct 284 ms 55216 KB Output is correct
56 Correct 412 ms 57136 KB Output is correct
57 Correct 313 ms 56292 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 8556 KB Output is correct
2 Correct 6 ms 8556 KB Output is correct
3 Correct 6 ms 8556 KB Output is correct
4 Correct 6 ms 8556 KB Output is correct
5 Correct 6 ms 8684 KB Output is correct
6 Correct 6 ms 8940 KB Output is correct
7 Correct 6 ms 8940 KB Output is correct
8 Correct 6 ms 8940 KB Output is correct
9 Correct 6 ms 8940 KB Output is correct
10 Correct 115 ms 40672 KB Output is correct
11 Correct 144 ms 47712 KB Output is correct
12 Correct 139 ms 47072 KB Output is correct
13 Correct 150 ms 49376 KB Output is correct
14 Correct 178 ms 50912 KB Output is correct
15 Correct 129 ms 40672 KB Output is correct
16 Correct 286 ms 49632 KB Output is correct
17 Correct 282 ms 53108 KB Output is correct
18 Correct 295 ms 55392 KB Output is correct
19 Correct 409 ms 56928 KB Output is correct
20 Correct 401 ms 52504 KB Output is correct
21 Correct 407 ms 58288 KB Output is correct
22 Correct 428 ms 57088 KB Output is correct
23 Correct 410 ms 58372 KB Output is correct
24 Correct 426 ms 57692 KB Output is correct
25 Correct 417 ms 55980 KB Output is correct
26 Correct 406 ms 57308 KB Output is correct
27 Correct 410 ms 55488 KB Output is correct
28 Correct 6 ms 8940 KB Output is correct
29 Correct 7 ms 8940 KB Output is correct
30 Correct 7 ms 8940 KB Output is correct
31 Correct 7 ms 8940 KB Output is correct
32 Correct 7 ms 8940 KB Output is correct
33 Correct 7 ms 8940 KB Output is correct
34 Correct 7 ms 8940 KB Output is correct
35 Correct 7 ms 8940 KB Output is correct
36 Correct 7 ms 8940 KB Output is correct
37 Correct 21 ms 14572 KB Output is correct
38 Correct 152 ms 51316 KB Output is correct
39 Correct 146 ms 51168 KB Output is correct
40 Correct 144 ms 51188 KB Output is correct
41 Correct 144 ms 50656 KB Output is correct
42 Correct 151 ms 50400 KB Output is correct
43 Correct 135 ms 46944 KB Output is correct
44 Correct 150 ms 51552 KB Output is correct
45 Correct 147 ms 51296 KB Output is correct
46 Correct 178 ms 53344 KB Output is correct
47 Correct 154 ms 51552 KB Output is correct
48 Correct 34 ms 14472 KB Output is correct
49 Correct 289 ms 55192 KB Output is correct
50 Correct 284 ms 55216 KB Output is correct
51 Correct 285 ms 55092 KB Output is correct
52 Correct 287 ms 54852 KB Output is correct
53 Correct 274 ms 52524 KB Output is correct
54 Correct 246 ms 42344 KB Output is correct
55 Correct 283 ms 56112 KB Output is correct
56 Correct 284 ms 55216 KB Output is correct
57 Correct 412 ms 57136 KB Output is correct
58 Correct 313 ms 56292 KB Output is correct
59 Correct 124 ms 20588 KB Output is correct
60 Correct 279 ms 54944 KB Output is correct
61 Correct 273 ms 53308 KB Output is correct
62 Correct 289 ms 56188 KB Output is correct
63 Correct 445 ms 57648 KB Output is correct
64 Correct 7 ms 8940 KB Output is correct
65 Correct 7 ms 8940 KB Output is correct
66 Correct 7 ms 9068 KB Output is correct
67 Correct 7 ms 9068 KB Output is correct
68 Correct 7 ms 8940 KB Output is correct
69 Correct 7 ms 9196 KB Output is correct
70 Correct 7 ms 9196 KB Output is correct
71 Correct 8 ms 9324 KB Output is correct
72 Correct 7 ms 9068 KB Output is correct
73 Correct 7 ms 9196 KB Output is correct
74 Correct 219 ms 61660 KB Output is correct
75 Correct 148 ms 51168 KB Output is correct
76 Correct 150 ms 51296 KB Output is correct
77 Correct 180 ms 54632 KB Output is correct
78 Correct 154 ms 51164 KB Output is correct
79 Correct 128 ms 42464 KB Output is correct
80 Correct 186 ms 54112 KB Output is correct
81 Correct 223 ms 68316 KB Output is correct
82 Correct 257 ms 72284 KB Output is correct
83 Correct 262 ms 78428 KB Output is correct
84 Correct 172 ms 53216 KB Output is correct
85 Correct 260 ms 72028 KB Output is correct
86 Correct 122 ms 28388 KB Output is correct
87 Correct 289 ms 55216 KB Output is correct
88 Correct 286 ms 55344 KB Output is correct
89 Correct 421 ms 56288 KB Output is correct
90 Correct 300 ms 57180 KB Output is correct
91 Correct 327 ms 54364 KB Output is correct
92 Correct 438 ms 56700 KB Output is correct
93 Correct 387 ms 71504 KB Output is correct
94 Correct 517 ms 76128 KB Output is correct
95 Correct 409 ms 82524 KB Output is correct
96 Correct 409 ms 57008 KB Output is correct
97 Correct 484 ms 65952 KB Output is correct