Submission #439732

#	Time	Username	Problem	Language	Result	Execution time	Memory
439732		soroush	통행료 (APIO13_toll)	C++17	16 / 100	13 ms	14796 KiB

toll

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int , int> pii;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 3e5 + 10;
const ll mod = 1e9+7;

#define pb push_back
#define endl '\n'
#define dokme(x) cout << x , exit(0)
#define ms(x , y) memset(x , y , sizeof x)
ll pw(ll a, ll b, ll md = mod){ll res = 1;while(b){if(b&1){res=(a*res)%md;}a=(a*a)%md;b>>=1;}return(res);}

int n, m , k;
int a[maxn], b[maxn], c[maxn] , srt[maxn] , p[maxn];
int L[maxn], R[maxn];

ll ans = 0 , sum = 0;
int par[maxn];
vector < int > adj[maxn];
bool mark[maxn];

int getpar(int v){
	return ((par[v]) ? par[v] = getpar(par[v]) : v);
}

ll dfs(int v){
	mark[v] = 1;
	ll ans = p[v];
	for(auto u : adj[v]){
		if(!mark[a[u]])ans += dfs(a[u]);
		if(!mark[b[u]])ans += dfs(b[u]);
	}
	return ans;
}

int32_t main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin >> n >> m >> k;
	assert(k == 1);
	for(int i = 0 ; i < m ; i ++)
		cin >> a[i] >> b[i] >> c[i] , srt[i] = i;
	sort(srt , srt + m , [](int i , int j){return c[i] < c[j];});
	for(int i = 0 ; i < k ; i ++)	
		cin >> L[i] >> R[i];
	for(int i = 1 ; i <= n ; i ++)
		cin >> p[i] , sum += p[i];
	for(int i = 0 ; i < m ; i ++){
		if(getpar(a[srt[i]]) == getpar(b[srt[i]]))continue;
		par[getpar(a[srt[i]])] = getpar(b[srt[i]]);
		if(getpar(L[0]) == getpar(R[0]) and !ans){
			//hell no!
			ans = c[srt[i]];
		}
		else{
			adj[a[srt[i]]].pb(srt[i]);
			adj[b[srt[i]]].pb(srt[i]);
		}
	}
	cout << ans * (sum - dfs(1));
	return(0);
}

• Subtask 1: 16 / 16
• Subtask 2: 0 / 18
• Subtask 3: 0 / 22
• Subtask 4: 0 / 22
• Subtask 5: 0 / 22