QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#267585#7869. 建设终末树hos_lyric#0 641ms207596kbC++1412.7kb2023-11-27 14:47:492024-07-04 03:09:44

Judging History

你现在查看的是最新测评结果

  • [2024-07-04 03:09:44]
  • 评测
  • 测评结果:0
  • 用时:641ms
  • 内存:207596kb
  • [2023-11-27 14:47:49]
  • 提交

answer

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")


struct Scc {
  int n;
  vector<int> as, bs;
  vector<int> ptr, zu, us;

  int l;
  vector<int> ids;
  int operator[](int u) const { return ids[u]; }

  explicit Scc(int n_) : n(n_), as(), bs(), l(-1) {}
  void ae(int u, int v) {
    assert(0 <= u); assert(u < n);
    assert(0 <= v); assert(v < n);
    as.push_back(u);
    bs.push_back(v);
  }

  void dfs0(int u) {
    if (!ids[u]) {
      ids[u] = -1;
      for (int i = ptr[u]; i < ptr[u + 1]; ++i) dfs0(zu[i]);
      us.push_back(u);
    }
  }
  void dfs1(int u) {
    if (!~ids[u]) {
      ids[u] = l;
      for (int i = ptr[u]; i < ptr[u + 1]; ++i) dfs1(zu[i]);
    }
  }
  void run() {
    const int m = as.size();
    ptr.resize(n + 2);
    zu.resize(m);
    for (int u = 0; u < n + 2; ++u) ptr[u] = 0;
    for (int i = 0; i < m; ++i) ++ptr[as[i] + 2];
    for (int u = 2; u < n + 1; ++u) ptr[u + 1] += ptr[u];
    for (int i = 0; i < m; ++i) zu[ptr[as[i] + 1]++] = bs[i];
    ids.assign(n, 0);
    us.clear();
    for (int u = 0; u < n; ++u) dfs0(u);
    for (int u = 0; u < n + 2; ++u) ptr[u] = 0;
    for (int i = 0; i < m; ++i) ++ptr[bs[i] + 2];
    for (int u = 2; u < n + 1; ++u) ptr[u + 1] += ptr[u];
    for (int i = 0; i < m; ++i) zu[ptr[bs[i] + 1]++] = as[i];
    l = 0;
    for (int j = n; --j >= 0; ) if (!~ids[us[j]]) { dfs1(us[j]); ++l; }
  }

  vector<vector<int>> group() const {
    assert(~l);
    vector<vector<int>> uss(l);
    for (int u = 0; u < n; ++u) uss[ids[u]].push_back(u);
    return uss;
  }
};


struct Hld {
  int n, rt;
  // needs to be tree
  // vertex lists
  // modified in build(rt) (parent removed, heavy child first)
  vector<vector<int>> graph;
  vector<int> sz, par, dep;
  int zeit;
  vector<int> dis, fin, sid;
  // head vertex (minimum depth) in heavy path
  vector<int> head;

  Hld() : n(0), rt(-1), zeit(0) {}
  explicit Hld(int n_) : n(n_), rt(-1), graph(n), zeit(0) {}
  void ae(int u, int v) {
    assert(0 <= u); assert(u < n);
    assert(0 <= v); assert(v < n);
    graph[u].push_back(v);
    graph[v].push_back(u);
  }

  void dfsSz(int u) {
    sz[u] = 1;
    for (const int v : graph[u]) {
      auto it = std::find(graph[v].begin(), graph[v].end(), u);
      if (it != graph[v].end()) graph[v].erase(it);
      par[v] = u;
      dep[v] = dep[u] + 1;
      dfsSz(v);
      sz[u] += sz[v];
    }
  }
  void dfsHld(int u) {
    dis[u] = zeit++;
    const int deg = graph[u].size();
    if (deg > 0) {
      int vm = graph[u][0];
      int jm = 0;
      for (int j = 1; j < deg; ++j) {
        const int v = graph[u][j];
        if (sz[vm] < sz[v]) {
          vm = v;
          jm = j;
        }
      }
      swap(graph[u][0], graph[u][jm]);
      head[vm] = head[u];
      dfsHld(vm);
      for (int j = 1; j < deg; ++j) {
        const int v = graph[u][j];
        head[v] = v;
        dfsHld(v);
      }
    }
    fin[u] = zeit;
  }
  void build(int rt_) {
    assert(0 <= rt_); assert(rt_ < n);
    rt = rt_;
    sz.assign(n, 0);
    par.assign(n, -1);
    dep.assign(n, -1);
    dep[rt] = 0;
    dfsSz(rt);
    zeit = 0;
    dis.assign(n, -1);
    fin.assign(n, -1);
    head.assign(n, -1);
    head[rt] = rt;
    dfsHld(rt);
    assert(zeit == n);
    sid.assign(n, -1);
    for (int u = 0; u < n; ++u) sid[dis[u]] = u;
  }

  friend ostream &operator<<(ostream &os, const Hld &hld) {
    const int maxDep = *max_element(hld.dep.begin(), hld.dep.end());
    vector<string> ss(2 * maxDep + 1);
    int pos = 0, maxPos = 0;
    for (int j = 0; j < hld.n; ++j) {
      const int u = hld.sid[j];
      const int d = hld.dep[u];
      if (hld.head[u] == u) {
        if (j != 0) {
          pos = maxPos + 1;
          ss[2 * d - 1].resize(pos, '-');
          ss[2 * d - 1] += '+';
        }
      } else {
        ss[2 * d - 1].resize(pos, ' ');
        ss[2 * d - 1] += '|';
      }
      ss[2 * d].resize(pos, ' ');
      ss[2 * d] += std::to_string(u);
      if (maxPos < static_cast<int>(ss[2 * d].size())) {
        maxPos = ss[2 * d].size();
      }
    }
    for (int d = 0; d <= 2 * maxDep; ++d) os << ss[d] << '\n';
    return os;
  }

  bool contains(int u, int v) const {
    return (dis[u] <= dis[v] && dis[v] < fin[u]);
  }
  int lca(int u, int v) const {
    assert(0 <= u); assert(u < n);
    assert(0 <= v); assert(v < n);
    for (; head[u] != head[v]; ) (dis[u] > dis[v]) ? (u = par[head[u]]) : (v = par[head[v]]);
    return (dis[u] > dis[v]) ? v : u;
  }
  int jumpUp(int u, int d) const {
    assert(0 <= u); assert(u < n);
    assert(d >= 0);
    if (dep[u] < d) return -1;
    const int tar = dep[u] - d;
    for (u = head[u]; ; u = head[par[u]]) {
      if (dep[u] <= tar) return sid[dis[u] + (tar - dep[u])];
    }
  }
  int jump(int u, int v, int d) const {
    assert(0 <= u); assert(u < n);
    assert(0 <= v); assert(v < n);
    assert(d >= 0);
    const int l = lca(u, v);
    const int du = dep[u] - dep[l], dv = dep[v] - dep[l];
    if (d <= du) {
      return jumpUp(u, d);
    } else if (d <= du + dv) {
      return jumpUp(v, du + dv - d);
    } else {
      return -1;
    }
  }
  // [u, v) or [u, v]
  template <class F> void doPathUp(int u, int v, bool inclusive, F f) const {
    assert(contains(v, u));
    for (; head[u] != head[v]; u = par[head[u]]) f(dis[head[u]], dis[u] + 1);
    if (inclusive) {
      f(dis[v], dis[u] + 1);
    } else {
      if (v != u) f(dis[v] + 1, dis[u] + 1);
    }
  }
  // not path order, include lca(u, v) or not
  template <class F> void doPath(int u, int v, bool inclusive, F f) const {
    const int l = lca(u, v);
    doPathUp(u, l, false, f);
    doPathUp(v, l, inclusive, f);
  }

  // (vs, ps): compressed tree
  // vs: DFS order (sorted by dis)
  // vs[ps[x]]: the parent of vs[x]
  // ids[vs[x]] = x, not set for non-tree vertex
  vector<int> ids;
  pair<vector<int>, vector<int>> compress(vector<int> us) {
    // O(n) first time
    ids.resize(n, -1);
    std::sort(us.begin(), us.end(), [&](int u, int v) -> bool {
      return (dis[u] < dis[v]);
    });
    us.erase(std::unique(us.begin(), us.end()), us.end());
    int usLen = us.size();
    assert(usLen >= 1);
    for (int x = 1; x < usLen; ++x) us.push_back(lca(us[x - 1], us[x]));
    std::sort(us.begin(), us.end(), [&](int u, int v) -> bool {
      return (dis[u] < dis[v]);
    });
    us.erase(std::unique(us.begin(), us.end()), us.end());
    usLen = us.size();
    for (int x = 0; x < usLen; ++x) ids[us[x]] = x;
    vector<int> ps(usLen, -1);
    for (int x = 1; x < usLen; ++x) ps[x] = ids[lca(us[x - 1], us[x])];
    return make_pair(us, ps);
  }
};

////////////////////////////////////////////////////////////////////////////////


int N, M, Q;
vector<int> A, B;
vector<vector<int>> C;
vector<vector<int>> V, S;

int main() {
  for (; ~scanf("%d%d%d", &N, &M, &Q); ) {
    A.resize(N - 1);
    B.resize(N - 1);
    for (int i = 0; i < N - 1; ++i) {
      scanf("%d%d", &A[i], &B[i]);
      --A[i];
      --B[i];
    }
    C.resize(M);
    for (int m = 0; m < M; ++m) {
      int len;
      scanf("%d", &len);
      C[m].resize(len);
      for (int &c : C[m]) {
        scanf("%d", &c);
        --c;
      }
    }
    V.resize(Q);
    S.resize(Q);
    for (int q = 0; q < Q; ++q) {
      int len;
      scanf("%d", &len);
      V[q].resize(len);
      for (int &v : V[q]) {
        scanf("%d", &v);
        --v;
      }
      scanf("%d", &len);
      S[q].resize(len);
      for (int &s : S[q]) {
        scanf("%d", &s);
        --s;
      }
    }
    
    Hld hld(N);
    for (int i = 0; i < N - 1; ++i) {
      hld.ae(A[i], B[i]);
    }
    hld.build(0);
    const auto &par = hld.par;
    const auto &sid = hld.sid;
#ifdef LOCAL
cerr<<string(80,'=')<<endl;
cerr<<hld<<endl;
cerr<<"C = "<<C<<endl;
cerr<<"V = "<<V<<endl;
cerr<<"S = "<<S<<endl;
#endif
    
    // m < M: item m is in subtree(u)
    // m >= M: all items in S[q] must be in subtree(u)
    auto tru = [&](int m, int u) -> int { return (m * N + u) << 1; };
    auto fal = [&](int m, int u) -> int { return (m * N + u) << 1 | 1; };
    auto pre = [&](int m, int u) -> int { return ((M + Q) * N + (m * N + u) * 2) << 1; };
    auto suf = [&](int m, int u) -> int { return ((M + Q) * N + (m * N + u) * 2 + 1) << 1; };
    Scc scc(((M + Q) * N + M * N * 2) << 1);
    // x ==> y
    auto add = [&](int x, int y) -> void {
      if (x != y) {
        scc.ae(x, y);
        if ((x ^ 1) != y) {
          scc.ae(y ^ 1, x ^ 1);
        }
      }
    };
    
    for (int m = 0; m < M; ++m) {
      vector<int> dp(N, 0);
      for (const int c : C[m]) {
        dp[c] += 1;
      }
      for (int j = N; --j >= 1; ) {
        const int u = sid[j];
        dp[par[u]] += dp[u];
      }
      for (int u = 0; u < N; ++u) {
        if (dp[u] == (int)C[m].size()) add(fal(m, u), tru(m, u));
        if (dp[u] == 0) add(tru(m, u), fal(m, u));
      }
      for (int u = 1; u < N; ++u) {
        add(tru(m, u), tru(m, par[u]));
      }
      for (int u = 0; u < N; ++u) {
        const auto &vs = hld.graph[u];
        /*
        for (int j0 = 0; j0 < (int)vs.size(); ++j0) for (int j1 = j0 + 1; j1 < (int)vs.size(); ++j1) {
          add(tru(m, vs[j0]), fal(m, vs[j1]));
        }
        */
        const int len = vs.size();
        for (int j = 1; j < len; ++j) {
          add(pre(m, vs[j - 1]), pre(m, vs[j]));
          add(suf(m, vs[j]), pre(m, vs[j - 1]));
        }
        for (int j = 0; j < len; ++j) {
          add(tru(m, vs[j]), pre(m, vs[j]));
          add(tru(m, vs[j]), suf(m, vs[j]));
          if (j - 1 >= 0) add(tru(m, vs[j]), pre(m, vs[j - 1]) ^ 1);
          if (j + 1 < len) add(tru(m, vs[j]), suf(m, vs[j + 1]) ^ 1);
        }
      }
    }
    
    for (int q = 0; q < Q; ++q) {
      /*
      vector<int> dp(N, 0);
      for (const int v : V[q]) {
        dp[v] += 1;
      }
      for (int j = N; --j >= 1; ) {
        const int u = sid[j];
        dp[par[u]] += dp[u];
      }
      for (int u = 0; u < N; ++u) {
        if (dp[u] == (int)V[q].size()) continue;
        if (dp[u] == 0) continue;
        // same side when cut (par[u], u)
        for (const int m0 : S[q]) for (const int m1 : S[q]) {
          add(tru(m0, u), tru(m1, u));
        }
      }
      */
      const auto vsps = hld.compress(V[q]);
      const int len = vsps.first.size();
// cerr<<V[q]<<": "<<vsps<<endl;
      for (int j = 1; j < len; ++j) {
        const int p = vsps.first[vsps.second[j]];
        for (int u = vsps.first[j]; u != p; u = par[u]) {
          // same side when cut (par[u], u)
          for (const int m : S[q]) {
            add(tru(m, u), tru(M + q, u));
          }
          for (const int m : S[q]) {
            add(tru(M + q, u), tru(m, u));
          }
        }
      }
    }
    
    scc.run();
    bool ok = true;
    for (int x = 0; x < scc.n; x += 2) {
      ok = ok && (scc[x] != scc[x ^ 1]);
    }
    if (ok) {
      vector<int> ans(M, -1);
      for (int m = 0; m < M; ++m) {
// for(int u=0;u<N;++u)cerr<<(scc[fal(m,u)]<scc[tru(m,u)]);cerr<<endl;
        for (int j = N; --j >= 0; ) {
          const int u = sid[j];
          if (scc[fal(m, u)] < scc[tru(m, u)]) {
            ans[m] = u;
            break;
          }
        }
      }
      for (int m = 0; m < M; ++m) {
        if (m) printf(" ");
        printf("%d", ans[m] + 1);
      }
      puts("");
    } else {
      puts("-1");
    }
  }
  return 0;
}

详细

Subtask #1:

score: 0
Time Limit Exceeded

Test #1:

score: 0
Time Limit Exceeded

input:

1999 1998 27199
1368 233
233 617
233 388
233 1127
1905 233
907 233
233 40
233 1325
233 1940
1739 233
501 233
233 33
735 233
233 283
233 1427
1992 233
233 632
233 685
1188 233
648 233
233 344
233 1321
986 233
848 233
770 233
256 233
164 233
936 233
1206 233
53 233
1054 233
1430 233
1714 233
86 233
11...

output:


result:


Subtask #2:

score: 0
Wrong Answer

Test #8:

score: 0
Wrong Answer
time: 1ms
memory: 3648kb

input:

10 10 8
4 2
2 9
6 9
8 7
4 10
7 2
5 2
2 1
5 3
3 10 7 2
2 10 2
2 4 10
2 10 4
2 8 2
2 4 10
1 8
2 2 10
1 1
1 10
2 10 9
3 10 3 4
2 7 1
3 10 6 3
2 4 8
2 3 2
4 2 9 4 6
2 5 7
2 3 9
2 2 1
4 10 6 8 5
4 10 6 1 2
2 1 4
2 7 5
2 5 3
2 8 3

output:

-1

result:

wrong answer jury find the answer, but you don't.

Subtask #3:

score: 0
Wrong Answer

Test #19:

score: 0
Wrong Answer
time: 641ms
memory: 207596kb

input:

500 498 5000
60 409
462 125
461 410
42 178
133 372
137 265
358 27
450 294
45 454
76 405
132 118
333 331
365 230
114 218
112 377
49 429
60 299
488 95
85 362
89 33
426 308
427 198
468 481
289 363
195 430
61 21
162 55
12 487
395 85
79 475
391 215
244 351
331 43
452 186
247 271
224 390
206 347
447 165
9...

output:

-1

result:

wrong answer jury find the answer, but you don't.

Subtask #4:

score: 0
Skipped

Dependency #2:

0%

Subtask #5:

score: 0
Skipped

Dependency #3:

0%

Subtask #6:

score: 0
Skipped

Dependency #1:

0%