제출 #1223279

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1223279		sleepntsheep	도로 개발 (JOI15_road_development)	C++17	100 / 100	537 ms	8568 KiB

road_development

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>

#define N 250005
int n, nq, tot;

using namespace std;

struct LCT {
	struct node {
		int rev, c[2], fa;
		int ed, sumed, pave, sumpave, lz;
	} t[N];

	void tagrev(int v) {
		if (! v) return;
		swap(t[v].c[0], t[v].c[1]);
		t[v].rev ^= 1;
	}
	void applypave(int v) {
		if (! v) return;
		t[v].sumpave=t[v].sumed;
		t[v].pave=t[v].ed;
		t[v].lz=1;
	}
	void pushup(int v) {
		if (! v) return;
		t[v].sumed = t[t[v].c[0]].sumed + t[t[v].c[1]].sumed + t[v].ed;
		t[v].sumpave=t[t[v].c[0]].sumpave+t[t[v].c[1]].sumpave+t[v].pave;
		//printf(" %d now %d %d\n", v,t[v].sumed,t[v].sumpave);
	}
	void pushdown(int v) {
		if (! v) return;
		if (t[v].rev) {
			tagrev(t[v].c[0]), tagrev(t[v].c[1]);
			t[v].rev = 0;
		}
		if (t[v].lz) {
			applypave(t[v].c[0]), applypave(t[v].c[1]);
			t[v].lz = 0;
		}
	}
	int nrt(int v) {
		return t[t[v].fa].c[0] == v || t[t[v].fa].c[1] == v;
	}
	void rot(int v) {
		int p, g, d;
		g = t[p = t[v].fa].fa, d = t[p].c[1] == v;
		if (nrt(p)) t[g].c[t[g].c[1] == p] = v;
		pushdown(v);
	
		if (t[v].c[!d])
			t[t[v].c[!d]].fa = p;
		t[p].c[d] = t[v].c[!d];
		t[v].c[!d] = p;

		t[v].fa = g, t[p].fa = v;
		pushup(p), pushup(v), pushup(g);
	}
	void update(int v) { if (nrt(v)) update(t[v].fa); pushdown(v); }
	void splay(int v) {
		update(v);
		for (int p; nrt(v); rot(v))
			if (nrt(p = t[v].fa))
				rot((t[p].c[0] == v) == (t[t[p].fa].c[0] == p) ? p : v);
		pushup(v);
	}
	int access(int v) {
		int w;
		for (w = 0; v; v = t[w = v].fa)
			splay(v), t[v].c[1] = w, pushup(v);
		return w;
	}
	void makeroot(int v) {
		access(v), splay(v), tagrev(v);
	}
	void split(int v, int w) {
		makeroot(v), access(w), splay(w);
	}
	void link(int v, int w) {
		split(v, w);
		t[v].fa = w;
	}
	int froot(int v) {
		access(v),splay(v);
		while (t[v].c[0]){
			//printf(" %d -> %d\n", v, t[v].c[0]);
			v=t[v].c[0];
		}
		splay(v);
		return v;
	}
}l;

int main() {
	scanf("%d%d", &n, &nq);
	tot = n;
	for (int Ti, a, b; nq--;) {
		scanf("%d%d%d", &Ti, &a, &b);
		if (Ti == 1) {
			if (l.froot(a) != l.froot(b)) {
				++tot;l.t[tot].ed=1;l.pushup(tot);
				l.link(a,tot),l.link(b,tot);
			}else{
				l.split(a,b);
				l.applypave(b);
			}
		} else {
			if (l.froot(a) != l.froot(b))
				puts("-1");
			else{
				l.split(a,b);
				//printf("%d %d\n",l.t[b].sumed,l.t[b].sumpave);
				printf("%d\n",l.t[b].sumed-l.t[b].sumpave);
			}
		}
	}

	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

road_development.cpp: In function 'int main()':
road_development.cpp:98:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   98 |         scanf("%d%d", &n, &nq);
      |         ~~~~~^~~~~~~~~~~~~~~~~
road_development.cpp:101:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |                 scanf("%d%d%d", &Ti, &a, &b);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 25 / 25
• Subtask 5: 15 / 15