Submission #22592

#	Time	Username	Problem	Language	Result	Execution time	Memory
22592		AcornCkiGs14004Team (#40)	Logistical Metropolis (KRIII5_LM)	C++11	0 / 7	2000 ms	1048576 KiB

LM

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int, int> pi;
typedef long long lint;
typedef long long int lli;

const int maxd = 22;
const int maxn = 50000 + 10;
const int INF = 0x3f3f3f3f;

struct Node {
	int x, y, w, k, id;
	void init(int tx, int ty, int tw, int i) {
		id = i;
		x = tx;
		y = ty;
		w = tw;
	}
	bool operator<(const Node& rhs) const { return w < rhs.w; }
} A[maxd][300001];

struct Modify {
	int k, d;
	void init(int tk, int td) {
		k = tk;
		d = td;
	 }
} B[1200001];
lint pr[1200005];
int cnt;

struct UnionFindSet {
	int pa[maxn];
	void init(int n) {
		for (int i = 1; i <= n; i++) pa[i] = i;
	}
	int find(int x) { return x == pa[x] ? x : (pa[x] = find(pa[x])); }
} ufs;

struct CDQ {
	int pa[maxn], dis[300005], pos[300005];

	void init(int m) {
		for (int i = 1; i <= m; i++) dis[A[0][i].id] = A[0][i].w;
	}

	// cur depth : d
	// modify sequence : [L, R]
	// points : n, edges : m
	void solve(int d, int L, int R, int n, int m, lli ans = 0LL) {
		for (int i = 1; i <= m; i++) {
			Node &a = A[d][i], &a2 = A[d - 1][i];
			a = (Node){a2.x, a2.y, dis[a2.id], 0, a2.id};
			pos[a.id] = i;
		}
		if (L == R) {
			Modify& b = B[L];
			A[d][pos[b.k]].w = dis[b.k] = b.d;
			ufs.init(n);
			sort(A[d] + 1, A[d] + m + 1);
			for (int i = 1; i <= m; i++) {
				Node& a = A[d][i];
				int x = ufs.find(a.x), y = ufs.find(a.y);
				if (x != y) {
					ufs.pa[y] = x;
					ans = ans + a.w;
				}
			}
			cnt++;
			if(pr[cnt]) printf("%lld\n", ans + pr[cnt]);
			return;
		}

		// reduction
		for (int i = L; i <= R; i++) A[d][pos[B[i].k]].k = 1;  // tag of in {S}
	ufs.init(n);
	sort(A[d] + 1, A[d] + m + 1);
	for (int i = 1; i <= m; i++)
		if (A[d][i].k == 0) {
			Node& a = A[d][i];
			int x = ufs.find(a.x), y = ufs.find(a.y);
			if (x != y) {
				ufs.pa[y] = x;
				a.k = 2;  // tag of in {T}
			}
		}

	// contraction
	for (int i = 1; i <= m; i++)
		if (A[d][i].k == 1) A[d][i].w = -INF;
	ufs.init(n);
	sort(A[d] + 1, A[d] + m + 1);
	for (int i = 1; i <= m; i++)
		if (A[d][i].k != 0) {
			Node& a = A[d][i];
			int x = ufs.find(a.x), y = ufs.find(a.y);
			if (x != y) {
				ufs.pa[y] = x;
				if (a.k != 1) a.k = 3;  // tag of in {T'-S}
			}
		}

	// rebuild
	ufs.init(n);
	for (int i = 1; i <= m; i++)
		if (A[d][i].k == 3) {
			Node& a = A[d][i];
			int x = ufs.find(a.x), y = ufs.find(a.y);
			ufs.pa[y] = x;
			ans = ans + a.w;
		}
	int newn = 0, newm = 0;
	for (int i = 1; i <= n; i++) pa[i] = 0;
	for (int i = 1; i <= n; i++) {
		int x = ufs.find(i);
		if (!pa[x]) pa[x] = ++newn;
	}
	for (int i = 1; i <= m; i++)
		if (A[d][i].k != 0) {
			Node& a = A[d][i];
			int x = ufs.find(a.x), y = ufs.find(a.y);
			if (x != y) A[d][++newm] = (Node){pa[x], pa[y], a.w, a.k, a.id};
		}

	int M = (L + R) >> 1;
	solve(d + 1, L, M, newn, newm, ans);
	solve(d + 1, M + 1, R, newn, newm, ans);
	}

} cdq;

vector<pi> gph[100005];

int main() {
	int n, m, q;
	scanf("%d %d", &n, &m);
	for(int i=1; i<=m; i++){
		int s, e, x;
		scanf("%d %d %d",&s,&e,&x);
		gph[s].push_back(pi(i, x));
		gph[e].push_back(pi(i, x));
		A[0][i].init(s, e, x, i);
	}
	q = 0;
	for(int i=1; i<=n; i++){
		lint s = 0;
		for(auto &j : gph[i]){
			B[++q].init(j.first, 0);
			s += j.second;
		}	
		pr[q] = s;
		for(auto &j : gph[i]){
			B[++q].init(j.first, j.second);
		}
	}
	cdq.init(m);
	cdq.solve(1, 1, q, n, m);
	return 0;
}

Compilation message (stderr)

LM.cpp: In function 'int main()':
LM.cpp:138:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
                        ^
LM.cpp:141:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d",&s,&e,&x);
                             ^

• Subtask 1: 0 / 2
• Subtask 2: 0 / 5