제출 #405895

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
405895		amunduzbaev	자매 도시 (APIO20_swap)	C++14	0 / 100	206 ms	27420 KiB

swap

#include "swap.h"
#include "bits/stdc++.h"
using namespace std;
#define pb push_back
#define ff first
#define ss second
#define sz(x) (int)x.size()
#define int long long

const int NN = 1e5+5;
int sub, used[NN], found, pos[NN], is[NN];
vector<int> pref[NN];
vector<pair<int, int>> edges[NN];
vector<pair<int, int>> ss;

void dfs(int u, int p = -1){
	if(used[u]){ found = 1; return; } 
	used[u] = 1;
	//cout<<u<<" ";
	for(auto x : edges[u]) { 
		if(x.ff == p) continue;
		ss.pb({u, x.ss});
		dfs(x.ff, u);
	}
}

void init(int32_t N, int32_t M,
	vector<int32_t> U, vector<int32_t> V, vector<int32_t> W) {
	//cout<<"\n";
	for(int i=0;i<M;i++){
		edges[U[i]].pb({V[i], W[i]});
		edges[V[i]].pb({U[i], W[i]});
	}
	int last = 0;
	for(int i=0;i<N;i++){
		if(used[i]) continue;
		ss.clear(), found = 0;
		dfs(i);
		if(found){
			pref[last].pb(0);
			ss.pop_back();
			for(int j=0;j<sz(ss);j++){
				is[ss[j].ff] = last+1;
				pos[ss[j].ff] = j+1;
				pref[last].pb(ss[j].ss);
			} for(int j=1;j<=sz(ss);j++) pref[last][j] += pref[last][j-1];
			last++;
		}
	} 
}

/*

5 5
1 0 1
2 1 2
3 2 3
4 3 4
4 0 5
5
0 1
1 2
2 3
3 4
4 0

*/

int32_t getMinimumFuelCapacity(int32_t x, int32_t y) {
	if(x > y) swap(x, y);
	if(is[x] != is[y] || !is[x]) return -1;
	int l = is[x] - 1;
	int i = pos[x], j = pos[y];
	if(i > j) swap(i, j);
	return max(pref[l][j-1] - pref[l][i-1], pref[l][i-1] + pref[l][sz(pref[l])-1] - pref[l][j-1]);
}

• Subtask 1: 0 / 6
• Subtask 2: 0 / 7
• Subtask 3: 0 / 17
• Subtask 4: 0 / 20
• Subtask 5: 0 / 23
• Subtask 6: 0 / 27