oj.uz

Submission #27102

# Submission time Handle Problem Language Result Execution time Memory
27102 2017-07-09T09:05:01 Z 검수컵(#1129) 2017 Apocalypse (FXCUP2_apocalypse) C++
0 / 1
 0 ms 20060 KB 
#include<stdio.h>
#include<algorithm>
using namespace std;

typedef long long lld;
const lld mod = 1000000009;

struct edg {
	int s, e; lld v;
	bool operator< (const edg& c) const {
		return v>c.v;
	}
} ba[303030];

int N; lld prob[303030]; // probability that each edge is in MST
int par[303030], vcn[303030]; lld vxs[303030], vxpxs[303030], vxpxsum;
lld ex2[303030], rv2[303030], dap1, dap2;

int root(int ix){ return par[ix]<0 ? ix : par[ix]=root(par[ix]); }

int main(){
	scanf("%d", &N);
	for(int i=0; i<N; i++) scanf("%d%d%lld", &ba[i].s, &ba[i].e, &ba[i].v);
	sort(ba, ba+N);
	ex2[0]=rv2[0]=1;
	for(int i=1; i<=N; i++) ex2[i]=ex2[i-1]*2%mod, rv2[i]=rv2[i-1]*500000005%mod;
	for(int i=0; i<=N; i++) par[i]=-1, vcn[i]=1;
	for(int i=0; i<N; i++){
		int s=root(ba[i].s), e=root(ba[i].e), k=root(0);
		int a=vcn[s], b=vcn[e];
		if(s==k){
			prob[i] = rv2[b];
			dap2 = (dap2 + (ba[i].v * rv2[b] % mod) * (vxs[e] + vxpxs[s])) % mod;
		}
		else if(e==k){
			prob[i] = rv2[a];
//			dap2 = (dap2 + (ba[i].v * rv2[a] % mod) * (vxs[s] + vxpxs[e])) % mod;
		}
		else{
			prob[i] = (ex2[a] + ex2[b] - 1) * rv2[a+b] % mod;
			dap2 = (dap2 + (ba[i].v * (ex2[a]-1) % mod) * (rv2[a+b] * vxs[e] % mod)) % mod;
			dap2 = (dap2 + ba[i].v * (rv2[a] * vxpxs[e] % mod)) % mod;
			dap2 = (dap2 + (ba[i].v * (ex2[b]-1) % mod) * (rv2[a+b] * vxs[s] % mod)) % mod;
			dap2 = (dap2 + ba[i].v * (rv2[b] * vxpxs[s] % mod)) % mod;
		}
		dap2 = (dap2 + (vxpxsum - vxpxs[s] - vxpxs[e] + mod*2) * (ba[i].v * prob[i] % mod)) % mod;
		vxpxsum = (vxpxsum + ba[i].v * prob[i]) % mod;

		if(vcn[s] > vcn[e]){
			par[e]=s; vcn[s]+=vcn[e];
			vxs[s] = (vxs[s] + vxs[e] + ba[i].v) % mod;
			vxpxs[s] = (vxpxs[s] + vxpxs[e] + ba[i].v*prob[i]) % mod;
		}
		else{
			par[s]=e; vcn[e]+=vcn[s];
			vxs[e] = (vxs[s] + vxs[e] + ba[i].v) % mod;
			vxpxs[e] = (vxpxs[s] + vxpxs[e] + ba[i].v*prob[i]) % mod;
		}
	}
	dap2 = dap2*2 % mod;

	for(int i=0; i<N; i++){
		dap1 = (dap1 + ba[i].v * prob[i]) % mod;
		dap2 = (dap2 + (ba[i].v * ba[i].v % mod) * prob[i]) % mod;
	}
	printf("%lld\n%lld\n", dap1 * ex2[N] % mod, dap2 * ex2[N] % mod);
	return 0;
}

Compilation message

apocalypse.cpp: In function 'int main()':
apocalypse.cpp:22:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
                 ^
apocalypse.cpp:23:72: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=0; i<N; i++) scanf("%d%d%lld", &ba[i].s, &ba[i].e, &ba[i].v);
                                                                        ^

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 20060 KB Output is correct
2 Correct 0 ms 20060 KB Output is correct
3 Incorrect 0 ms 20060 KB Output isn't correct
4 Halted 0 ms 0 KB -