oj.uz

Submission #287741

# Submission time Handle Problem Language Result Execution time Memory
287741 2020-08-31T23:01:04 Z Namnamseo Toll (APIO13_toll) C++17
78 / 100
 2500 ms 42744 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;
using pp=pair<int,int>;
#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;

inline int ri() { int x; scanf("%d", &x); return x; }

struct E { int a, b, c; bool operator<(const E& r)const{ return c<r.c; } } ek[30], eu[300010], et[500]; int eun, etn;
vector<pp> e0[int(1e6)+1];
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;

int g[100010],gn;
ll u[100010];

vector<pp> G[50];
vector<int> T[100010];
int P[100010];
ll s[50];

ll dfs(int x, int gn, int p) {
	ll ret = u[x]; g[x] = gn;
	for(int y:T[x]) if(p!=y) ret += dfs(y, gn, x);
	return ret;
}

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

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

bool seen[50][50];

int main() {
	n = ri(); m = ri(); k = ri();
	rep(i,m) {
		int a = ri(), b = ri(), c = ri();
		e0[c].eb(a, b);
	}

	rep(i,k) ek[i].a=ri(), ek[i].b=ri();
	rrep(i,n) u[i]=ri();

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

	rrep(i, int(1e6)) {
		for(auto [a, b]:e0[i]) {
			if (uf.join(a, b)) {
				T[a].pb(b);
				T[b].pb(a);
			} else {
				eu[eun++]={a, b, i};
			}
		}
	}

	rrep(i, n) if (!g[i]) ++gn, s[gn]=dfs(i, gn, -1);

	rep(i, eun) {
		int a=g[eu[i].a], b=g[eu[i].b];
		if (a>b) swap(a, b);
		if (a!=b && !seen[a][b]) seen[a][b]=1, et[etn++]={a, b, eu[i].c};
	}

	rep(i, k) ek[i].a=g[ek[i].a], ek[i].b=g[ek[i].b];

	ll O = 0;

	for(int m=1; m<(1<<k); ++m) {
		uf.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=e.a, b=e.b;
			if(a==b || !uf.join(a, b)) { mf=1; break; }
			--cc;
			ae(a, b, 1);
		}
		if (mf) continue;

		eun = 0;
		rep(j, etn){
			int a=et[j].a, b=et[j].b, &c=et[j].c;
			if(uf.join(a, b)) {
				ae(a, b, 0); --cc;
			} else eu[eun++]=et[j];
		}

		if (cc != 1) continue;

		gp[g[1]] = 0; gl[g[1]] = 0;
		gd(g[1]);

		for(int j=eun-1; 0<=j; --j) if (eu[j].c>0) {
			int a=eu[j].a, b=eu[j].b;
			if (gl[a]>gl[b]) swap(a, b);
			while (gl[a]<gl[b])
				ans[b] = eu[j].c, b=gp[b];
			while (a!=b) {
				ans[a] = eu[j].c;
				ans[b] = eu[j].c;
				a = gp[a]; b = gp[b];
			}
		}

		ll ca = 0;
		rrep(i, gn) if (ikc[i]) ca += ans[i] * S[i];

		O=max(O, ca);
	}

	printf("%lld\n", O);

	return 0;
}

Compilation message

toll.cpp: In function 'int main()':
toll.cpp:111:31: warning: unused variable 'c' [-Wunused-variable]
  111 |    int a=et[j].a, b=et[j].b, &c=et[j].c;
      |                               ^
toll.cpp: In function 'int ri()':
toll.cpp:20:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   20 | inline int ri() { int x; scanf("%d", &x); return x; }
      |                          ~~~~~^~~~~~~~~~

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 26112 KB Output is correct
2 Correct 20 ms 26108 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 26112 KB Output is correct
2 Correct 20 ms 26108 KB Output is correct
3 Correct 21 ms 26112 KB Output is correct
4 Correct 21 ms 26112 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 26112 KB Output is correct
2 Correct 20 ms 26108 KB Output is correct
3 Correct 21 ms 26112 KB Output is correct
4 Correct 21 ms 26112 KB Output is correct
5 Correct 25 ms 26368 KB Output is correct
6 Correct 25 ms 26368 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 26112 KB Output is correct
2 Correct 20 ms 26108 KB Output is correct
3 Correct 21 ms 26112 KB Output is correct
4 Correct 21 ms 26112 KB Output is correct
5 Correct 25 ms 26368 KB Output is correct
6 Correct 25 ms 26368 KB Output is correct
7 Correct 452 ms 42692 KB Output is correct
8 Correct 474 ms 42616 KB Output is correct
9 Correct 464 ms 42616 KB Output is correct

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 26112 KB Output is correct
2 Correct 20 ms 26108 KB Output is correct
3 Correct 21 ms 26112 KB Output is correct
4 Correct 21 ms 26112 KB Output is correct
5 Correct 25 ms 26368 KB Output is correct
6 Correct 25 ms 26368 KB Output is correct
7 Correct 452 ms 42692 KB Output is correct
8 Correct 474 ms 42616 KB Output is correct
9 Correct 464 ms 42616 KB Output is correct
10 Correct 1481 ms 42696 KB Output is correct
11 Execution timed out 2578 ms 42744 KB Time limit exceeded
12 Halted 0 ms 0 KB -