QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#163840#6123. JAG Graph IsomorphismrealIyxiang#WA 8ms32760kbC++143.3kb2023-09-04 15:42:272023-09-04 15:42:28

Judging History

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

  • [2023-09-04 15:42:28]
  • 评测
  • 测评结果:WA
  • 用时:8ms
  • 内存:32760kb
  • [2023-09-04 15:42:27]
  • 提交

answer

#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
#define rep(i, l, r) for (int i = l; i <= r; ++i)
const int N = 2e5 + 5;
const int base = 131; 
const int P1 = 1e9 + 9, P2 = 1e9 + 7; 
struct Graph {
  struct edge { int v, id; } ;
  vector <edge> G[N]; int cnt, num, sz[N], cir[N];
  pair <int, int> a[N], hax[N];
  void add (int u, int v, int id) {
    G[u].push_back((edge){v, id});
    G[v].push_back((edge){u, id}); 
  }
} T[2];
pair <pair <int, int>, int> tmp[N]; 
pair <int, int> s[N * 3]; 
int n, u, v, tp, cnt, num, z[N], pw1[N], pw2[N], st[N], dep[N], vis[N], book[N]; 

int inc (int a, int b, int P) { return (a += b) >= P ? a - P : a; }
int dec (int a, int b, int P) { return (a -= b) < 0 ? a + P : a; }
int mul (int a, int b, int P) { return 1ll * a * b % P; }
int fpow (int a, int b, int P) { int ans = 1; for ( ; b; a = mul(a, a, P), b >>= 1) if(b & 1) ans = mul(ans, a, P); return ans; }

int main () {
  ios :: sync_with_stdio(0), cin.tie(0), cout.tie(0); 
  cin >> n; 
  pw1[0] = pw2[0] = 1; 
  rep(i, 1, n) {
    pw1[i] = mul(pw1[i - 1], base, P1); 
    pw2[i] = mul(pw2[i - 1], base, P2); 
  }
  rep(i, 1, n) cin >> u >> v, T[0].add(u, v, i); 
  rep(i, 1, n) cin >> u >> v, T[1].add(u, v, i); 
  function <void(int, int, int)> dfs1 = [&](int o, int u, int f) {
    vis[u] = 1, st[++tp] = u, dep[u] = dep[f] + 1; 
    for (auto e : T[o].G[u]) if(!book[e.id]) {
      book[e.id] = 1; 
      if(!vis[e.v]) dfs1(o, e.v, u); 
      else if(dep[e.v] < dep[u]) {
        for ( ; st[tp] != e.v; --tp) T[o].cir[st[tp]] = 1, z[++num] = st[tp]; 
        T[o].cir[e.v] = 1, z[++num] = e.v;  
      }
    }
    --tp; 
  } ;
  function <void(int, int, int)> dfs2 = [&](int o, int u, int f) {
    T[o].sz[u] = 1, dep[u] = dep[f] + 1; 
    for (auto e : T[o].G[u]) if(!T[o].cir[e.v] && e.v != f) 
      dfs2(o, e.v, u); 
    cnt = 0; 
    for (auto e : T[o].G[u]) if(!T[o].cir[e.v] && e.v != f) 
      tmp[++cnt] = make_pair(T[o].hax[e.v], e.v); 
    sort(tmp + 1, tmp + cnt + 1); 
    rep(i, 1, cnt) {
      T[o].sz[u] += T[o].sz[tmp[i].second]; 
      T[o].hax[u].first = inc(T[o].hax[u].first, 
        mul(tmp[i].first.first, pw1[T[o].sz[u]], P1), P1);
      T[o].hax[u].second = inc(T[o].hax[u].second, 
        mul(tmp[i].first.second, pw2[T[o].sz[u]], P2), P2);
    }
    T[o].hax[u].first = inc(T[o].hax[u].first, mul(dep[u], pw1[1], P1), P1);
    T[o].hax[u].second = inc(T[o].hax[u].second, mul(dep[u], pw2[1], P2), P2);
  } ;
  dfs1(0, 1, 0); 
  rep(i, 1, num) {
    dfs2(0, z[i], 0), T[0].a[++T[0].num] = T[0].hax[z[i]]; 
  } 
  memset(vis, 0, sizeof(vis));
  memset(book, 0, sizeof(book)); 
  tp = num = 0, dfs1(1, 1, 0);
  rep(i, 1, num) {
    dfs2(1, z[i], 0), T[1].a[++T[1].num] = T[1].hax[z[i]]; 
  } 
  rep(i, 1, n) rep(j, 0, 1) T[j].cnt += T[j].cir[i]; 
  if(T[0].cnt != T[1].cnt) { puts("No"); return 0; }
  rep(i, 1, n) 
    s[i] = T[0].a[i], s[i + n] = s[i + 2 * n] = T[1].a[i]; 
  auto chk = [&]() {
    z[1] = 0, z[0] = -1; 
    rep(i, 2, n * 3) {
      int j = z[i - 1]; 
      for ( ; j != -1 && s[j + 1] != s[i]; j = z[j]) ;
      z[i] = j + 1; 
      if(z[i] == n) return true; 
    }
    return false; 
  } ;
  if(chk()) puts("Yes");  
  else puts("No"); 
  return 0; 
}

詳細信息

Test #1:

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

input:

4
1 2
2 3
2 4
3 4
1 2
1 3
1 4
3 4

output:

Yes

result:

ok answer is YES

Test #2:

score: 0
Accepted
time: 8ms
memory: 32760kb

input:

4
1 2
2 3
3 4
1 4
1 2
1 3
1 4
3 4

output:

No

result:

ok answer is NO

Test #3:

score: -100
Wrong Answer
time: 6ms
memory: 31308kb

input:

6
1 2
1 3
2 5
2 6
3 5
4 6
1 5
1 6
2 4
2 5
2 6
3 4

output:

No

result:

wrong answer expected YES, found NO