oj.uz

Submission #49406

# Submission time Handle Problem Language Result Execution time Memory
49406 2018-05-28T12:21:36 Z hamzqq9 Toll (APIO13_toll) C++14
100 / 100
 2124 ms 52988 KB 
#include<bits/stdc++.h>
#define lf double
#define ll long long
#define cc pair<char,char>
#define ull unsigned ll
#define ii pair<int,int>
#define li pair<ll,int>
#define iii pair<int,ii>
#define iiii pair<ii,ii>
#define iiii2 pair<int,iii>
#define lii pair<ll,ii>
#define lolo pair<ll,ll>
#define heap priority_queue
#define mp make_pair
#define st first
#define nd second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) x.begin(),x.end()
#define len(x) strlen(x)
#define sz(x) (int) x.size()
#define orta ((bas+son)/2)
#define min3(x,y,z) min(min(x,y),z)
#define max3(x,y,z) max(max(x,y),z)
#define umin(x,y) x=min(x,y)
#define umax(x,y) x=max(x,y)
#define dbgs(x) cerr<<(#x)<<" --> "<<(x)<<" "
#define dbg(x) cerr<<(#x)<<" --> "<<(x)<<endl;getchar()
#define MOD 1000000000
#define inf 1000000000
#define N 300005
#define LOG 20
#define magic 100
#define KOK 250
#define EPS 0.0025
#define pw(x) (1<<(x))
#define PI 3.1415926535
using namespace std;

int n,m,k,x,y,z,total;
int ata[N],baba[N],der[N],id[N],ind[N];
ll sub[N],population[N];
vector<ii> v[N];
vector<int> important,critical,unimportant;
ii my[N];
iii e[N];
ll ans;

void init(int node,int ata) {

	baba[node]=ata;

	der[node]=der[ata]+1;

	sub[node]=population[node];

	for(int i=0;i<sz(v[node]);i++) {

		ii go=v[node][i];

		if(go.st==ata) continue ;

		init(go.st,node);

		ind[go.st]=i;

		sub[node]+=sub[go.st];

	}

}

int bul(int node) {if(ata[node]==node) return node;return ata[node]=bul(ata[node]);}

bool merge(int x,int y) {

	if(bul(x)==bul(y)) return false;

	ata[bul(x)]=bul(y);

	return true;

}

void clear() {

	for(int i=1;i<=n;i++) {

		v[i].clear();

		ata[i]=i;

	}

}

int main() {
 
//	freopen("input.txt","r",stdin);
 
	scanf("%d %d %d",&n,&m,&k);

	for(int i=1;i<=m;i++) {

		scanf("%d %d %d",&x,&y,&z);

		e[i]={z,{x,y}};

	}

	for(int i=1;i<=k;i++) {

		scanf("%d %d",&x,&y);

		my[i]={x,y};

	}

	for(int i=1;i<=n;i++) {

		scanf("%lld",&population[i]);

	}

	clear();

	sort(e+1,e+1+m);

	for(int i=1;i<=k;i++) {

		merge(my[i].st,my[i].nd); 

	}

	for(int i=1;i<=m;i++) {

		if(merge(e[i].nd.st,e[i].nd.nd)) {

			important.pb(i);

		}
		else {

			unimportant.pb(i);

		}

	}

	clear();

	for(int ed:important) {

		population[bul(e[ed].nd.nd)]+=population[bul(e[ed].nd.st)];

		merge(e[ed].nd.st,e[ed].nd.nd);

	}

	int headofhead=bul(1);

	for(int i=1;i<=n;i++) {

		if(bul(i)==i) {

			total++;

			id[i]=total;

			population[total]=population[i];

		}

	}

	int nodeofhead=id[headofhead];

	n=total;

	for(int ed:unimportant) {	

		e[ed].nd.st=id[bul(e[ed].nd.st)];
		e[ed].nd.nd=id[bul(e[ed].nd.nd)];

	}

	for(int i=1;i<=k;i++) {

		my[i].st=id[bul(my[i].st)];
		my[i].nd=id[bul(my[i].nd)];

	}

	clear();

	for(int ed:unimportant) {

		if(merge(e[ed].nd.st,e[ed].nd.nd)) {

			critical.pb(ed);

		}

	}

	assert(sz(critical)<=k);

	m=sz(critical);

	for(int mask=1;mask<pw(k);mask++) {

		bool flag=0;

		clear();

		for(int i=1;i<=k;i++) {

			if(mask&pw(i-1)) {

				if(!merge(my[i].st,my[i].nd)) flag=1;

				v[my[i].st].pb({my[i].nd,inf});
				v[my[i].nd].pb({my[i].st,inf});

			}

		}

		if(flag) continue ;

		vector<int> query;

		for(int ed:critical) {

			if(!merge(e[ed].nd.st,e[ed].nd.nd)) {

				query.pb(ed);

			}
			else {

				v[e[ed].nd.st].pb({e[ed].nd.nd,e[ed].st});
				v[e[ed].nd.nd].pb({e[ed].nd.st,e[ed].st});

			}

		}

		init(nodeofhead,0);

		for(int q:query) {

			int node1=e[q].nd.st;
			int node2=e[q].nd.nd;

			if(der[node1]<der[node2]) swap(node1,node2);

			int d1=der[node1];
			int d2=der[node2];

			while(d1>d2) {

				umin(v[baba[node1]][ind[node1]].nd,e[q].st);
				
				d1--;
				node1=baba[node1];

			}

			while(node1!=node2) {

				umin(v[baba[node1]][ind[node1]].nd,e[q].st);
				umin(v[baba[node2]][ind[node2]].nd,e[q].st);

				node1=baba[node1];				
				node2=baba[node2];

			}

		}

		ll res=0;

		for(int i=1;i<=k;i++) {

			if(!(mask&pw(i-1))) continue ;

			int node1=my[i].st;
			int node2=my[i].nd;

			if(baba[node1]==node2) {

				res+=1ll*sub[node1]*v[node2][ind[node1]].nd;

			}
			else {

				res+=1ll*sub[node2]*v[node1][ind[node2]].nd;

			}

		}

		umax(ans,res);

	}

	printf("%lld",ans);

}

Compilation message

toll.cpp: In function 'int main()':
toll.cpp:103:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d",&n,&m,&k);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~
toll.cpp:107:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d",&x,&y,&z);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~
toll.cpp:115:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&x,&y);
   ~~~~~^~~~~~~~~~~~~~~
toll.cpp:123:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",&population[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7416 KB Output is correct
2 Correct 8 ms 7528 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7416 KB Output is correct
2 Correct 8 ms 7528 KB Output is correct
3 Correct 9 ms 7604 KB Output is correct
4 Correct 10 ms 7660 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7416 KB Output is correct
2 Correct 8 ms 7528 KB Output is correct
3 Correct 9 ms 7604 KB Output is correct
4 Correct 10 ms 7660 KB Output is correct
5 Correct 13 ms 8008 KB Output is correct
6 Correct 12 ms 8136 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7416 KB Output is correct
2 Correct 8 ms 7528 KB Output is correct
3 Correct 9 ms 7604 KB Output is correct
4 Correct 10 ms 7660 KB Output is correct
5 Correct 13 ms 8008 KB Output is correct
6 Correct 12 ms 8136 KB Output is correct
7 Correct 265 ms 20700 KB Output is correct
8 Correct 328 ms 27452 KB Output is correct
9 Correct 470 ms 33680 KB Output is correct

Subtask #5
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7416 KB Output is correct
2 Correct 8 ms 7528 KB Output is correct
3 Correct 9 ms 7604 KB Output is correct
4 Correct 10 ms 7660 KB Output is correct
5 Correct 13 ms 8008 KB Output is correct
6 Correct 12 ms 8136 KB Output is correct
7 Correct 265 ms 20700 KB Output is correct
8 Correct 328 ms 27452 KB Output is correct
9 Correct 470 ms 33680 KB Output is correct
10 Correct 1727 ms 40156 KB Output is correct
11 Correct 1936 ms 46584 KB Output is correct
12 Correct 2124 ms 52988 KB Output is correct