Submission #22852

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
22852	2017-04-30T07:51:55 Z	AcornCkiGs14004Team(#953, gs14004, cki86201, dotorya)	Logistical Metropolis (KRIII5_LM)	C++14	2 / 7	2000 ms	152912 KB

LM

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>

using namespace std;
typedef long long ll;
typedef pair<int, int> Pi;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define sz(x) (int)x.size()
#define rep(i, n) for(int i=0;i<n;i++)
#define all(x) x.begin(), x.end()
typedef pair<int, int> pii;
typedef tuple<int, int, int> t3;

struct node{
	node(){}
	node(int x){
		idx = x;
		rev = val = 0; mx = Pi(0, x);
		child[0] = child[1] = par = pp = 0;
	}
	Pi mx;
	int val, idx, rev;
	node *child[2], *par, *pp;
	inline int mydir(){
		return par->child[1] == this;
	}
	inline void pushdown(){
		if(rev){
			swap(child[0], child[1]);
			if(child[0])child[0]->rev ^= 1;
			if(child[1])child[1]->rev ^= 1;
			rev = 0;
		}
	}
	inline void pushup(){
		mx.Fi = val, mx.Se = idx;
		if(child[0] && child[0]->mx.Fi > mx.Fi)mx = child[0]->mx;
		if(child[1] && child[1]->mx.Fi > mx.Fi)mx = child[1]->mx;
	}
	void rotate(int dir){
		node *c = child[!dir];
		c->pushdown();
		if(par)par->child[mydir()] = c; c->par = par;
		if(pp)c->pp = pp, pp = 0;
		child[!dir] = c->child[dir];
		if(c->child[dir])c->child[dir]->par = this;
		c->child[dir] = this;
		par = c;
		pushup();
		c->pushup();
	}
	void splay(node *rootp){
		while(par != rootp){
			if(par->par == rootp){
				par->pushdown();
				par->rotate(!mydir());
			}
			else{
				par->par->pushdown();
				par->pushdown();
				int md = mydir();
				if(par->mydir() != md){
					par->rotate(!md);
					par->rotate(md);
				}
				else{
					par->par->rotate(!md);
					par->rotate(!md);
				}
			}
		}
	}
};

node *mem[2000010];
pii meme[2000040];

void access(node *v){
	v->splay(0); v->pushdown();
	if(v->child[1]){
		v->child[1]->par = 0, v->child[1]->pp = v;
		v->child[1] = 0; v->pushup();
	}
	while(v->pp){
		node *u = v->pp;
		u->splay(0); u->pushdown();
		if(u->child[1])u->child[1]->par = 0, u->child[1]->pp = u;
		u->child[1] = v;
		v->par = u; v->pp = 0;
		u->pushup();
		v->splay(0);
	}
}

void makeroot(node *v){
	access(v);
	v->rev ^= 1;
	v->pushdown();
}

int mz;

void link(int ux, int vx, int L){
	node *u = mem[ux];
	node *v = mem[vx];
	makeroot(v);
	++mz; mem[mz] = new node(mz);
	mem[mz]->val = L; mem[mz]->mx.Fi = L;
	meme[mz] = Pi(ux, vx);
	access(u);
	u->child[1] = mem[mz]; mem[mz]->par = u;
	mem[mz]->child[1] = v; v->par = mem[mz];
	mem[mz]->pushup(); u->pushup();
//	printf("link %d -- %d, %d\n", ux, mz, L); printf("link %d -- %d, %d\n", vx, mz, L);
}

void cut(int ux, int vx){
	node *u = mem[ux];
	node *v = mem[vx];
	access(u);
	v->splay(0);
	if(v->pp == u)v -> pp = 0;
	else{
		v->pushdown();
		v->child[1] = 0;
		v->pushup();
		u->par = 0;
	}
//	printf("cut %d -- %d\n", ux, vx);
}

/*
void link(int uv, int vv, int L){
	node *u = mem[uv], *v = mem[vv];
	makeroot(v);
	++mz; mem[mz] = new node(mz);
	mem[mz]->val = L; mem[mz]->mx.Fi = L;
	meme[mz] = Pi(uv, vv);
	access(u);
	u->child[1] = mem[mz]; mem[mz]->par = u;
	mem[mz]->child[1] = v; v->par = mem[mz];
	mem[mz]->pushup(); u->pushup();
}

void cut(int uv, int vv){
	node *u = mem[uv], *v = mem[vv];
	access(u);
	v->splay(0);
	if(v->pp == u){
		v->pp = 0;
	}
	else{
		v->pushdown();
		v->child[1] = 0;
		v->pushup();
		u->par = 0;
	}
}

void query(int x, int y, int l){
	node *u = mem[x], *v = mem[y];
	access(u);
	access(v);
	u->splay(0);
	Pi res;
	if(u->pp){
		res = u->mx;
		if(u->pp != v){
			node *w = u->pp;
			w->splay(0); w->pushdown();
			if(res.Fi < w->val)res = Pi(w->val, w->idx);
			if(res.Fi < w->child[1]->mx.Fi)res = w->child[1]->mx;
		}
	}
	else{
		res = Pi(u->val, u->idx);
		u->pushdown();
		if(res.Fi < u->child[1]->mx.Fi)res = u->child[1]->mx;
	}
	if(res.Fi <= l)return;
	ans -= res.Fi;
	ans += l;
	cut(res.Se, meme[res.Se].Fi);
	cut(res.Se, meme[res.Se].Se);
	link(x, y, l);
}
*/
 
int N, M;
vector <pii> E[100010];
ll ans;
int p[100010];
int Find(int x){return p[x] == x ? x : p[x] = Find(p[x]); }

void query(int x, int y, int l, ll &tans, pii &rr){
//	printf("Q%d %d\n", x, y);
	node *u = mem[x], *v = mem[y];
	access(u);
	access(v);
	u->splay(0);
	Pi res;
	if(u->pp){
		res = u->mx;
		if(u->pp != v){
			node *w = u->pp;
			w->splay(0); w->pushdown();
			if(res.Fi < w->val)res = Pi(w->val, w->idx);
			if(res.Fi < w->child[1]->mx.Fi)res = w->child[1]->mx;
		}
	}
	else{
		res = Pi(u->val, u->idx);
		u->pushdown();
		if(res.Fi < u->child[1]->mx.Fi)res = u->child[1]->mx;
	}
	tans -= res.Fi;
	cut(res.Se, meme[res.Se].Fi);
	cut(res.Se, meme[res.Se].Se);
	rr = res;
	link(x, y, l);
}

const int INF = -1e9-10;

set <pii> S;

void getInt(int &a){
	a = 0;
	char c;
	while(isdigit(c = getchar())){
		a = a * 10 + c - '0';
	}
}

void solve(){
	scanf("%d%d", &N, &M);
	vector <t3> V;
	rep(i, M){
		int x, y, z; scanf("%d%d%d", &x, &y, &z);
		if(x == y) continue;
		S.insert(pii(x, y));
		E[x].pb(pii(z, y));
		E[y].pb(pii(z, x));
		V.emplace_back(z, x, y);
	}
	mz = N;
	sort(all(V));
	for(int i=1;i<=N;i++)p[i] = i;
	for(int i=1;i<=N;i++)mem[i] = new node(i);
	for(int i=0;i<sz(V);i++){
		t3 &a = V[i];
		int x = Find(get<1>(a)), y = Find(get<2>(a));
		if(x != y){
			p[x] = y, ans += get<0>(a);
			int u = get<1>(a), v = get<2>(a);
			if(u > v)swap(u, v);
			link(u, v, get<0>(a));
		}
	}
	for(int i=1;i<=N;i++){
		ll tans = ans;
		vector <t3> W;
		vector <int> WX; WX.resize(sz(E[i]));
		rep(j, sz(E[i])){
			auto &e = E[i][j];
			tans += e.Fi;
			pii rr;
			query(i, e.Se, INF, tans, rr);
			int L = rr.Fi, x = meme[rr.Se].Fi, y = meme[rr.Se].Se;
			WX[j] = mz;
			W.emplace_back(x, y, L);
		}
		rep(j, sz(E[i])){
			int x = WX[j];
			cut(i, x);
			cut(E[i][j].Se, x);
		}
		for(t3 &e : W) link(get<0>(e), get<1>(e), get<2>(e));
		printf("%lld\n", tans);
		
	}
}

int main(){
	int Tc = 1; //scanf("%d\n", &Tc);
	for(int tc=1;tc<=Tc;tc++){
		solve();
	}
	return 0;
}

Compilation message

LM.cpp: In function 'void solve()':
LM.cpp:249:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &M);
                       ^
LM.cpp:252:43: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x, y, z; scanf("%d%d%d", &x, &y, &z);
                                           ^

Subtask #1

2.0 / 2.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	37124 KB	Output is correct
2	Correct	3 ms	37124 KB	Output is correct
3	Correct	9 ms	37212 KB	Output is correct
4	Correct	16 ms	37212 KB	Output is correct
5	Correct	16 ms	37212 KB	Output is correct
6	Correct	13 ms	37120 KB	Output is correct
7	Correct	13 ms	37124 KB	Output is correct
8	Correct	6 ms	37120 KB	Output is correct
9	Correct	9 ms	37124 KB	Output is correct
10	Correct	16 ms	37124 KB	Output is correct
11	Correct	13 ms	37124 KB	Output is correct
12	Correct	13 ms	37120 KB	Output is correct
13	Correct	3 ms	37252 KB	Output is correct
14	Correct	9 ms	37120 KB	Output is correct
15	Correct	6 ms	37120 KB	Output is correct
16	Correct	6 ms	37248 KB	Output is correct
17	Correct	9 ms	37248 KB	Output is correct
18	Correct	6 ms	37248 KB	Output is correct
19	Correct	13 ms	37244 KB	Output is correct
20	Correct	9 ms	37120 KB	Output is correct
21	Correct	6 ms	37248 KB	Output is correct
22	Correct	13 ms	37244 KB	Output is correct
23	Correct	9 ms	37248 KB	Output is correct
24	Correct	13 ms	37244 KB	Output is correct
25	Correct	0 ms	36016 KB	Output is correct
26	Correct	0 ms	36016 KB	Output is correct
27	Correct	0 ms	36016 KB	Output is correct
28	Correct	0 ms	36552 KB	Output is correct

Subtask #2

0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	2000 ms	152912 KB	Execution timed out
2	Halted	0 ms	0 KB	-