QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#189373#5201. Cactus Meets TorusckisekiRE 0ms3524kbC++203.7kb2023-09-27 13:43:512023-09-27 13:43:51

Judging History

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

  • [2023-09-27 13:43:51]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:3524kb
  • [2023-09-27 13:43:51]
  • 提交

answer

// An AC a day keeps the doctor away.
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#ifdef local
#define safe std::cerr<<__PRETTY_FUNCTION__<<" line "<<__LINE__<<" safe\n"
#define debug(args...) qqbx(#args, args)
#define orange(args...) danb(#args, args)
using std::cerr;
template <typename ...T> void qqbx(const char *s, T ...args) {
  int cnt = sizeof...(T);
  ((cerr << "\e[1;32m(" << s << ") = ("), ..., (cerr << args << (--cnt ? ", " : ")\e[0m\n")));
}
template <typename I> void danb(const char *s, I L, I R) {
  cerr << "\e[1;32m[ " << s << " ] = [ ";
  for (int f = 0; L != R; ++L) cerr << (f++ ? ", " : "") << *L;
  cerr << " ]\e[0m\n";
}
#else
#define safe ((void)0)
#define debug(...) ((void)0)
#define orange(...) ((void)0)
#endif // local
#define all(v) begin(v),end(v)

using namespace std;

struct RST {
  int n; vector<vector<int>> T;
  RST(auto &G) : n(G.size()), T(n) {
    vector<int> stk, vis(n), low(n);
    auto dfs = [&](auto self, int u, int d) -> void {
      low[u] = vis[u] = d; stk.push_back(u);
      for (int v : G[u]) if (!vis[v]) {
        self(self, v, d + 1);
        if (low[v] == vis[u]) {
          int cnt = T.size(); T.emplace_back();
          for (int x = -1; x != v; stk.pop_back())
            T[cnt].push_back(x = stk.back());
          T[u].push_back(cnt);
        } else low[u] = min(low[u], low[v]);
      } else low[u] = min(low[u], vis[v]);
    };
    dfs(dfs, 0, 1);
  }
};

signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, m;
  while (cin >> n >> m && (n || m)) {
    vector<vector<int>> g(n);
    for (int i = 0; i < m; i++) {
      int k;
      cin >> k;
      vector<int> p(k);
      for (int &x: p) cin >> x, --x;
      for (int j = 1; j < k; j++) {
        int a = p[j - 1], b = p[j];
        g[a].emplace_back(b);
        g[b].emplace_back(a);
      }
    }

    RST tr(g);

    vector<int> bcc(tr.T.size());
    int k = 0;

    for (size_t i = n; i < tr.T.size(); i++) {
      if (tr.T[i].size() + 1 >= 3) {
        bcc[i] = true;
        ++k;
      }
    }

    if (k == 0) {
      cout << "Yes\n";
      continue;
    }

    vector<vector<int>> nt(tr.T.size());

    for (size_t i = 0; i < tr.T.size(); i++) {
      for (int j: tr.T[i]) {
        cerr << i << ' ' << j << endl;
      }
    }

    vector<int> cnt(tr.T.size());
    const auto dfs = [&](auto self, int i) -> void {
      cnt[i] = bcc[i];
      for (int j: tr.T[i]) {
        self(self, j);
        if (cnt[j] != 0 && cnt[j] != k) {
          nt[i].emplace_back(j);
          nt[j].emplace_back(i);
        }
        cnt[i] += cnt[j];
      }
    };

    dfs(dfs, 0);

    int root = -1;
    for (size_t i = n; i < tr.T.size(); i++)
      if (bcc[i] && nt[i].size() == 1) {
        root = i;
        break;
      }
    assert (root != -1);

    int dfc = 0;
    vector<int> tin(tr.T.size()), tou(tr.T.size());
    vector<int> pa(tr.T.size());
    const auto dfs2 = [&](auto self, int i, int f) -> void {
      pa[i] = f;
      tin[i] = dfc++;
      for (int j: nt[i]) {
        if (j == f) continue;
        self(self, j, i);
      }
      tou[i] = dfc;
    };
    dfs2(dfs2, root, -1);

    vector<int> z;
    for (size_t i = n; i < tr.T.size(); i++)
      if (bcc[i]) {
        int x = i;
        if (pa[x] != -1) x = pa[x];
        if (pa[x] != -1) x = pa[x];
        z.push_back(x);
      }
    sort(z.begin(), z.end(), [&](int a, int b) { return tin[a] < tin[b]; });
    bool ok = true;
    for (size_t i = 1; i < z.size(); i++) {
      int x = z[i - 1];
      int y = z[i];
      ok &= tin[x] <= tin[y] && tin[y] < tou[x];
    }
    if (ok) {
      cout << "Yes\n";
    } else {
      cout << "No\n";
    }

  }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3524kb

input:

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

output:

Yes
No

result:

ok 2 token(s): yes count is 1, no count is 1

Test #2:

score: -100
Runtime Error

input:

15 3
9 1 2 3 4 5 6 7 8 3
7 2 9 10 11 12 13 10
5 2 14 9 15 10
15 7
3 1 2 3
3 4 2 5
3 6 2 7
3 8 2 9
3 10 2 11
3 12 2 13
3 14 2 15
1 0
2 1
2 1 2
2 1
2 2 1
3 1
4 1 3 2 1
4 2
3 1 2 3
2 2 4
6 2
5 1 2 3 4 5
2 4 6
7 3
5 1 2 3 4 5
2 4 6
2 4 7
7 2
6 1 2 3 4 5 6
2 5 7
8 3
6 1 2 3 4 5 6
2 5 7
2 5 8
9 4
5 1 2 3 ...

output:

Yes
Yes
Yes
Yes
Yes

result: