oj.uz

Submission #439732

# Submission time Handle Problem Language Result Execution time Memory
439732 2021-06-30T16:58:54 Z soroush Toll (APIO13_toll) C++17
16 / 100
 13 ms 14796 KB 
#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.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7372 KB Output is correct
2 Correct 5 ms 7500 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7372 KB Output is correct
2 Correct 5 ms 7500 KB Output is correct
3 Runtime error 13 ms 14796 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7372 KB Output is correct
2 Correct 5 ms 7500 KB Output is correct
3 Runtime error 13 ms 14796 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7372 KB Output is correct
2 Correct 5 ms 7500 KB Output is correct
3 Runtime error 13 ms 14796 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7372 KB Output is correct
2 Correct 5 ms 7500 KB Output is correct
3 Runtime error 13 ms 14796 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -