oj.uz

Submission #287683

# Submission time Handle Problem Language Result Execution time Memory
287683 2020-08-31T22:17:19 Z Namnamseo Toll (APIO13_toll) C++17
78 / 100
 2500 ms 22584 KB 
#include <sys/types.h>
#include <sys/stat.h>
#include <sys/mman.h>
#include <unistd.h>
#include <algorithm>
#include <numeric>
#include <cstring>
#include <vector>
#include <cstdio>
using namespace std;
using ll=long long;
#define rep(i,n) for(int i=0;i<n;++i)
#define rrep(i,n) for(int i=1;i<=n;++i)
#define pb push_back
#define eb emplace_back

int n, m, k;

char *I;
int ri() { int ret=0; while (*I<48||*I>=58) ++I; while(*I>=48&&*I<58) ret=ret*10+(*(I++)-48); return ret; }
char Y[20];

struct E { int a, b, c; bool operator<(const E& r)const{ return c<r.c; } } e0[300010], ek[20], eu[300010], et[500]; int eun, etn;
struct UF { int p[100010]; void init(int s=n){iota(p+1,p+s+1,1);} int r(int x){return x==p[x]?x:(p[x]=r(p[x])); }
int join(int a,int b){ a=r(a);b=r(b); if(a==b) return 0;p[a]=b;return 1; }} uf, uf2, ufk;

int g[100010],r[100010],gn;
ll u[100010];
int md[50][50];

using pp=pair<int,int>;
vector<pp> G[50];
vector<int> T[100010];
int P[100010];
ll s[100010];

void dfs(int x){
	s[x]=u[x];
	for(int y:T[x]) if(P[x]!=y) {
		P[y]=x; dfs(y);
		s[x]+=s[y];
	}
}

ll S[50];
int gp[50], gl[50];
int kc[50], kcn;
int ans[50];
void gd(int x) {
	S[x] = s[r[x]];
	for(auto [y, d]:G[x]) if (y != gp[x]) {
		gp[y] = x; gl[y] = gl[x]+1;
		if (d) { kc[kcn++] = y; }
		gd(y); S[x] += S[y];
	}
}

int glca(int a, int b) {
	if (gl[a] > gl[b]) return glca(b, a);
	while (gl[a]!=gl[b]) b=gp[b];
	while (a!=b) a=gp[a], b=gp[b];
	return a;
}

void ae(int a, int b, int c) {
	G[a].pb({b, c});
	G[b].pb({a, c});
}

int main() {
	setbuf(stdout, 0);
	{ static char buf[100]; using Z=struct stat*; fstat(0, (Z)buf); I=(char*)mmap(0,Z(buf)->st_size,1,2,0,0);}
	n = ri(); m = ri(); k = ri();
	rep(i,m) e0[i].a=ri(), e0[i].b=ri(), e0[i].c=ri();
	rep(i,k) ek[i].a=ri(), ek[i].b=ri();
	rrep(i,n) u[i]=ri();

	uf.init(); uf2.init(); rep(i,k) uf.join(ek[i].a,ek[i].b);

	static int q[300010];
	iota(q,q+m,0); sort(q,q+m,[&](const int&a,const int&b){ return e0[a]<e0[b]; });

	rep(i,m) {
		auto&e=e0[q[i]];
		if (uf.join(e.a, e.b)) {
			uf2.join(e.a, e.b);
			T[e.a].pb(e.b);
			T[e.b].pb(e.a);
		} else {
			eu[eun++]=e;
		}
	}

	rrep(i,n) if (uf2.p[i]==i) r[g[i]=++gn]=i;
	rrep(i,n) if (uf2.p[i]!=i) g[i]=g[uf2.r(i)];

	memset(md,0x7f,sizeof(md));
	rep(i,eun) {
		int a = g[eu[i].a];
		int b = g[eu[i].b];
		if (a != b) md[b][a]=md[a][b]=min(md[a][b], eu[i].c);
	}

	rrep(i, gn) dfs(r[i]);

	ll O = 0;

	const int inf = 0x7f7f7f7f;

	for(int m=1; m<(1<<k); ++m) {
		ufk.init(gn);
		rrep(x, gn) G[x].clear();

		bool mf=0;
		int cc=gn;
		rep(j,k) if (1&(m>>j)) {
			auto &e = ek[j];
			int a=g[e.a], b=g[e.b];
			if(a==b || !ufk.join(a, b)) { mf=1; break; }
			--cc;
			ae(a, b, 1);
		}
		if (mf) continue;

		etn=0;
		rrep(x, gn) rrep(y, x-1)
			if(md[x][y] != inf)
				et[etn++] = {x, y, md[x][y]};

		sort(et,et+etn);

		rep(j, etn){
			int a=et[j].a, b=et[j].b, c=et[j].c;
			if(ufk.join(a, b)) {
				ae(a, b, 0); --cc;
				et[j].c = 0;
			}
		}

		if (cc != 1) continue;

		kcn = 0;
		gp[g[1]] = 0; gl[g[1]] = 0;
		gd(g[1]);
		rep(i, kcn) ans[kc[i]] = inf;

		rep(j, etn) if (et[j].c) {
			int a=et[j].a, b=et[j].b, l = glca(a, b);
			for(int x:{a, b}) {
				while (x != l) {
					ans[x] = min(ans[x], et[j].c);
					x = gp[x];
				}
			}
		}

		ll ca = 0;
		rep(i, kcn) ca += ans[kc[i]] * S[kc[i]];

		O=max(O, ca);
	}

	for(gn=0;!gn||O;)Y[gn++]=48+O%10, O/=10;
	reverse(Y,Y+gn); Y[gn]=10; write(1,Y,gn+1);

	return 0;
}

Compilation message

toll.cpp: In function 'int main()':
toll.cpp:133:30: warning: unused variable 'c' [-Wunused-variable]
  133 |    int a=et[j].a, b=et[j].b, c=et[j].c;
      |                              ^
toll.cpp:164:34: warning: ignoring return value of 'ssize_t write(int, const void*, size_t)', declared with attribute warn_unused_result [-Wunused-result]
  164 |  reverse(Y,Y+gn); Y[gn]=10; write(1,Y,gn+1);
      |                             ~~~~~^~~~~~~~~~

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 4 ms 2736 KB Output is correct
4 Correct 3 ms 2688 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 4 ms 2736 KB Output is correct
4 Correct 3 ms 2688 KB Output is correct
5 Correct 6 ms 2940 KB Output is correct
6 Correct 5 ms 2940 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 4 ms 2736 KB Output is correct
4 Correct 3 ms 2688 KB Output is correct
5 Correct 6 ms 2940 KB Output is correct
6 Correct 5 ms 2940 KB Output is correct
7 Correct 213 ms 22452 KB Output is correct
8 Correct 335 ms 22480 KB Output is correct
9 Correct 313 ms 22584 KB Output is correct

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 4 ms 2736 KB Output is correct
4 Correct 3 ms 2688 KB Output is correct
5 Correct 6 ms 2940 KB Output is correct
6 Correct 5 ms 2940 KB Output is correct
7 Correct 213 ms 22452 KB Output is correct
8 Correct 335 ms 22480 KB Output is correct
9 Correct 313 ms 22584 KB Output is correct
10 Correct 1882 ms 22552 KB Output is correct
11 Execution timed out 2581 ms 22560 KB Time limit exceeded
12 Halted 0 ms 0 KB -