제출 #49406

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
49406		hamzqq9	통행료 (APIO13_toll)	C++14	100 / 100	2124 ms	52988 KiB

toll

#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);

}

컴파일 시 표준 에러 (stderr) 메시지

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 / 16
• Subtask 2: 18 / 18
• Subtask 3: 22 / 22
• Subtask 4: 22 / 22
• Subtask 5: 22 / 22