Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdio>
- #include <cstdlib>
- #include <cstring>
- #include <algorithm>
- #include <cmath>
- #include <vector>
- #include <map>
- #include <set>
- #include <ctime>
- #include <cassert>
- #include <queue>
- using namespace std;
- #define f first
- #define s second
- #define mp make_pair
- #define pb push_back
- #define forit(it,con) for (typeof(con.begin()) it = con.begin(); it != con.end(); ++it)
- #define f0(a) memset(a, 0, sizeof(a))
- #define all(v) v.begin(), v.end()
- #define pii pair<int,int>
- #define vi vector<int>
- #ifdef WIN32
- #define I64 "%I64d"
- #else
- #define I64 "%lld"
- #endif
- struct Cartesian {
- struct Tree {
- Tree *l, *r;
- int sz, y;
- bool rev;
- Tree() {
- l = r = 0;
- sz = y = 0;
- rev = false;
- }
- };
- int Count(Tree *v) {
- if (!v) return 0;
- return v -> sz;
- }
- void norm(Tree *v) {
- if (!v) return;
- v -> sz = Count(v -> l) + Count(v -> r) + 1;
- }
- void Push(Tree *v) {
- if (!v) return;
- if (!v -> rev) return;
- swap(v -> l, v -> r);
- if (v -> l) v -> l -> rev ^= 1;
- if (v -> r) v -> r -> rev ^= 1;
- v -> rev = 0;
- }
- Tree *Merge(Tree *l, Tree *r) {
- if (!l) return r;
- if (!r) return l;
- Push(l); Push(r);
- if (l -> y > r -> y) {
- l -> r = Merge(l -> r, r);
- norm(l);
- return l;
- } else {
- r -> l = Merge(l, r -> l);
- norm(r);
- return r;
- }
- }
- void split(Tree *root, int x, Tree *&l, Tree *&r) {
- if (!root) {
- l = r = 0;
- return;
- }
- if (Count(root->l) + 1 <= x) {
- Split(root -> r, x - Count(root -> l) - 1, root -> r, r);
- norm(root);
- } else {
- Split(root -> l, x, l, root -> l);
- norm(root);
- }
- }
- };
- int main() {
- #ifdef LOCAL
- freopen("in", "r", stdin);
- freopen("out", "w", stdout);
- #endif
- while (true) {
- scanf("%d%d%d%d", &n, &m, &c, &t);
- if (n == 0) break;
- for (int i = 0; i < m; ++i) {
- int u, v, k;
- scanf("%d%d%d", &u, &v, &k);
- g[k][u].pb(v);
- g[k][v].pb(u);
- Map[mp(u,v)] = Map[mp(v, u)] = k;
- }
- for (int i = 1; i <= n; ++i)
- used[i] = 0;
- for (int col = 1; col <= c; ++col) {
- for (int i = 1;i <= n; ++i)
- if (g[col][i].size() == 1) {
- Tn++;
- int v = i;
- while (true) {
- T[Tn - 1].add(v);
- used[v] = col;
- bool found = false;
- forit(it,g[col][v]) {
- if (used[*it] != col) {v = *it; found = true; break;}
- }
- if (!found) break;
- }
- }
- }
- for (int it = 0; it < t; ++it) {
- int u, v, k;
- scanf("%d%d%d", &u, &v, &k);
- if (!Map.count(mp(u,v))) {
- puts("No such cable.");
- continue;
- }
- int col = Map[mp(u,v)];
- if (col == k) {
- puts("Already owned.");
- continue;
- }
- if (deg[k][u] == 2 || deg[k][v] == 2) {
- puts("Forbidden: monopoly.");
- continue;
- }
- if (next[k][u] == v) {
- puts("Forbidden: redundanet.");
- continue;
- }
- puts("Sold.");
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment