[BZOJ 3651] 네트워크 통신 [Link - Cut Tree]
엘 시 티 100 개 만 열 면 장난 칠 수 있어.
/* Pigonometry */
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <utility>
using namespace std;
typedef pair<int, int> pii;
const int maxn = 8005, maxc = 101, maxs = 100000;
int n, m, c;
map<pii, int> com;
int sta[maxs], top;
struct _lct {
int son[maxn][2], pre[maxn], deg[maxn];
bool rev[maxn];
void init() {
for(int i = 0; i < maxn; i++) son[i][0] = son[i][1] = pre[i] = deg[i] = 0;
}
bool isroot(int x) {
return son[pre[x]][0] != x && son[pre[x]][1] != x;
}
void pushdown(int x) {
if(rev[x]) {
int l = son[x][0], r = son[x][1];
rev[l] ^= 1; rev[r] ^= 1;
swap(son[l][0], son[l][1]); swap(son[r][0], son[r][1]);
rev[x] = 0;
}
}
void rotate(int x) {
int y = pre[x], z = pre[y], type = son[y][1] == x;
pre[son[y][type] = son[x][!type]] = y;
pre[x] = z;
if(!isroot(y)) son[z][son[z][1] == y] = x;
pre[son[x][!type] = y] = x;
}
void maintain(int x) {
top = 0;
for(sta[++top] = x; !isroot(x); x = pre[x]) sta[++top] = pre[x];
for(; top; pushdown(sta[top--]));
}
void splay(int x) {
maintain(x);
while(!isroot(x)) {
int y = pre[x], z = pre[y];
if(isroot(y)) rotate(x);
else if(son[y][1] == x ^ son[z][1] == y) rotate(x), rotate(x);
else rotate(y), rotate(x);
}
}
void access(int x) {
for(int y = 0; x; x = pre[y = x]) {
splay(x);
son[x][1] = y;
}
}
void makeroot(int x) {
access(x); splay(x); rev[x] ^= 1;
swap(son[x][0], son[x][1]);
}
void link(int x, int y) {
makeroot(x); pre[x] = y;
deg[x]++; deg[y]++;
}
void cut(int x, int y) {
makeroot(x); access(y); splay(y);
deg[x]--; deg[y]--;
son[y][0] = pre[x] = 0;
}
int findroot(int x) {
access(x); splay(x);
for(; son[x][0]; x = son[x][0]);
return x;
}
bool check(int x, int y) {
return findroot(x) == findroot(y);
}
} lct[maxc];
inline int iread() {
int f = 1, x = 0; char ch = getchar();
for(; ch < '0' || ch > '9'; ch = getchar()) f = ch == '-' ? -1 : 1;
for(; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
return f * x;
}
int main() {
n = iread(); m = iread(); c = iread(); int T = iread();
for(int i = 1; i <= c; i++) lct[i].init();
for(int i = 1; i <= m; i++) {
int u = iread(), v = iread(), w = iread();
lct[w].link(u, v);
com[pii(u, v)] = com[pii(v, u)] = w;
}
while(T--) {
int u = iread(), v = iread(), w = iread();
int tmp = com[pii(u, v)];
if(tmp == 0) printf("No such cable.
");
else if(tmp == w) printf("Already owned.
");
else if(lct[w].deg[u] == 2 || lct[w].deg[v] == 2) printf("Forbidden: monopoly.
");
else if(lct[w].check(u, v)) printf("Forbidden: redundant.
");
else {
lct[tmp].cut(u, v);
com[pii(u, v)] = com[pii(v, u)] = w;
lct[w].link(u, v);
printf("Sold.
");
}
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.