oj.uz

Submission #122402

# Submission time Handle Problem Language Result Execution time Memory
122402 2019-06-28T07:12:58 Z 조승현(#2994) Toll (APIO13_toll) C++14
100 / 100
 1580 ms 25248 KB 
#include<stdio.h>
#include<algorithm>
#include<list>
#define N_ 101000
#define LIT list<Edge3>::iterator
using namespace std;
int N, M, K, Renum[N_], C, P[N_];
long long SZ[30], Res;
struct Edge {
	int a, b, c;
	bool operator <(const Edge &p)const {
		return c < p.c;
	}
}Ed[301000];

struct Edge2 {
	int a, b;
}w[30];

struct Edge3 {
	int a, b, gap;
	bool ck;
}tp, par2[N_], def_E[30];
list <Edge3> E[N_];

int par[N_];

int find(int a) {
	if (a == par[a])return a;
	return par[a] = find(par[a]);
}

void init() {
	int i, x, y;
	for (i = 1; i <= N; i++) {
		par[i] = i;
	}
	for (i = 0; i < M; i++) {
		x = find(Ed[i].a), y = find(Ed[i].b);
		if (x == y)continue;
		par[x] = y;
		tp.a = Ed[i].a, tp.b = Ed[i].b, tp.gap = Ed[i].c, tp.ck = false;
		E[Ed[i].a].push_back(tp);
		tp.a = Ed[i].b, tp.b = Ed[i].a;
		E[Ed[i].b].push_back(tp);
	}
}

int Q[N_];

void BFS(int a) {
	int h = 0, t = 0, x;
	LIT it;
	Q[++t] = a, par2[a].a = a;
	while (h < t) {
		x = Q[++h];
		for (it = E[x].begin(); it != E[x].end(); it++) {
			if (!par2[it->b].a) {
				Q[++t] = it->b;
				par2[it->b] = *it;
			}
		}
	}
}
int cnt;
void Modify(int a, int b, int c) {
	LIT it;
	for (it = E[a].begin(); it != E[a].end(); it++) {
		if (it->b == b) {
			if (c == -1) {
				E[a].erase(it);
				break;
			}
			else it->gap = c;
		}
	}
}

void DFS(int a) {
	LIT it;
	Renum[a] = C;
	SZ[C] = SZ[C] + P[a];
	for (it = E[a].begin(); it != E[a].end(); it++) {
		if (!(it->ck) && !Renum[it->b]) {
			DFS(it->b);
		}
	}
}

void Make_Compress() {
	int i, x, y;
	for (i = 1; i <= N; i++) {
		if (!Renum[i]) {
			C++;
			DFS(i);
		}
	}
	for (i = 1; i <= N; i++)E[i].clear();
	for (i = 0; i < cnt; i++) {
		x = Renum[def_E[i].a], y = Renum[def_E[i].b];
		tp.a = x, tp.b = y, tp.ck = false, tp.gap = def_E[i].gap;
		E[x].push_back(tp);
		tp.a = y, tp.b = x;
		E[y].push_back(tp);
	}
	N = C;
}

long long DP[30], Sum;

void DFS2(int a) {
	DP[a] += SZ[a];
	LIT it;
	for (it = E[a].begin(); it != E[a].end(); it++) {
		if (DP[it->b])continue;
		DFS2(it->b);
		if (it->ck) {
			Sum += DP[it->b] * (long long)it->gap;
		}
		DP[a] += DP[it->b];
	}
	return;
}

long long Calc()
{
	int i;
	for (i = 1; i <= N; i++)DP[i] = 0;
	Sum = 0;
	DFS2(1);
	return Sum;
}

void Make_MST(int a, bool ck) {
	if (a == K) {
		if (!ck) Make_Compress();
		else {
			long long t = Calc();
			if (Res < t)Res = t;
		}
		return;
	}
	if (ck)Make_MST(a + 1, ck);
	int i, x = w[a].a, y = w[a].b, Max = -1, ma, mb, ty, cc = 0;
	Edge3 TP[22];
	if (ck)x = Renum[x], y = Renum[y];
	ty = y;
	for (i = 1; i <= N; i++) {
		par2[i].a = 0;
	}
	BFS(x);
	while (y != x) {
		if (!par2[y].ck && Max < par2[y].gap) {
			ma = y, mb = par2[y].a, Max = par2[y].gap;
		}
		y = par2[y].a;
	}
	if (Max == -1) {
		Make_MST(a + 1, ck);
		return;
	}
	if (!ck) def_E[cnt].a = ma, def_E[cnt].b = mb, def_E[cnt++].gap = Max;
	Modify(ma, mb, -1);
	Modify(mb, ma, -1);
	y = ty;
	tp.a = x, tp.b = y, tp.gap = Max, tp.ck = true;
	E[x].push_back(tp);
	tp.a = y, tp.b = x;
	E[y].push_back(tp);
	while (y != x) {
		if (par2[y].ck && Max < par2[y].gap) {
			TP[cc++] = par2[y];
			Modify(y, par2[y].a, Max);
			Modify(par2[y].a, y, Max);
		}
		y = par2[y].a;
	}
	Make_MST(a + 1, ck);
	if (!ck)return;
	y = ty;
	Modify(x, y, -1);
	Modify(y, x, -1);
	tp.a = ma, tp.b = mb, tp.gap = Max, tp.ck = false;
	E[ma].push_back(tp);
	tp.a = mb, tp.b = ma;
	E[mb].push_back(tp);
	for (i = 0; i < cc; i++) {
		Modify(TP[i].a, TP[i].b, TP[i].gap);
		Modify(TP[i].b, TP[i].a, TP[i].gap);
	}
}
int main()
{
	int i;
	scanf("%d%d%d", &N, &M, &K);
	for (i = 0; i < M; i++) {
		scanf("%d%d%d", &Ed[i].a, &Ed[i].b, &Ed[i].c);
	}
	sort(Ed, Ed + M);
	for (i = 0; i < K; i++) {
		scanf("%d%d", &w[i].a, &w[i].b);
	}
	for (i = 1; i <= N; i++) {
		scanf("%d", &P[i]);
	}
	init();
	Make_MST(0, 0);
	Make_MST(0, 1);
	printf("%lld\n", Res);
	return 0;
}

Compilation message

toll.cpp: In function 'int main()':
toll.cpp:195: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:197:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &Ed[i].a, &Ed[i].b, &Ed[i].c);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:201:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &w[i].a, &w[i].b);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:204:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &P[i]);
   ~~~~~^~~~~~~~~~~~~

Subtask #1
16.0 / 16.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
22.0 / 22.0

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

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2688 KB Output is correct
2 Correct 4 ms 2688 KB Output is correct
3 Correct 4 ms 2688 KB Output is correct
4 Correct 4 ms 2688 KB Output is correct
5 Correct 7 ms 2956 KB Output is correct
6 Correct 7 ms 2944 KB Output is correct
7 Correct 621 ms 18700 KB Output is correct
8 Correct 634 ms 18716 KB Output is correct
9 Correct 608 ms 18788 KB Output is correct

Subtask #5
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2688 KB Output is correct
2 Correct 4 ms 2688 KB Output is correct
3 Correct 4 ms 2688 KB Output is correct
4 Correct 4 ms 2688 KB Output is correct
5 Correct 7 ms 2956 KB Output is correct
6 Correct 7 ms 2944 KB Output is correct
7 Correct 621 ms 18700 KB Output is correct
8 Correct 634 ms 18716 KB Output is correct
9 Correct 608 ms 18788 KB Output is correct
10 Correct 1228 ms 18920 KB Output is correct
11 Correct 1506 ms 25248 KB Output is correct
12 Correct 1580 ms 25224 KB Output is correct