QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #79979 | #5307. Subgraph Isomorphism | ybw20051114 | WA | 3ms | 6188kb | C++14 | 6.0kb | 2023-02-21 15:52:40 | 2023-10-15 17:24:40 |
Judging History
answer
/*******************************
| Author: ybw051114
| Problem: %$Problem$%
| Contest: %$Contest$%
| URL: %$URL$%
| When: %$Time$%
|
| Memory: %$MemoryL$% MB
| Time: %$TimeL$% ms
*******************************/
#include <bits/stdc++.h>
#ifndef use_ios11
#define use_ios11
using namespace std;
#define log(a) cerr << "\033[32m[DEBUG] " << #a << '=' << (a) << " @ line " << __LINE__ << "\033[0m" << endl
typedef long long ll;
#define pb push_back
typedef pair<int, int> pii;
#define mem(p) memset(&p, 0, sizeof(p))
typedef pair<long long, long long> pll;
#define ir(x) \
int x; \
yin >> x
#define foor(action, actionx2, actionx4, width) \
do \
{ \
unsigned long __width = (unsigned long)(width); \
unsigned long __increment = __width >> 2; \
for (; __increment > 0; __increment--) \
{ \
actionx4; \
} \
switch (__width & 3) \
{ \
case 2: \
actionx2; \
break; \
case 3: \
actionx2; \
case 1: \
action; \
break; \
} \
} while (0)
struct ins
{
int ans;
ins()
{
ans = 1;
}
#define endl '\n'
void read()
{
}
void read1(char &s)
{
char c = getchar();
for (; !isprint(c) || c == ' ' || c == '\n' || c == '\t'; c = getchar())
;
s = c;
if (c == EOF)
ans = 0;
}
void read1(string &s)
{
s = "";
char c = getchar();
for (; !isprint(c) || c == ' ' || c == '\n' || c == '\t'; c = getchar())
;
for (; isprint(c) && c != ' ' && c != '\n' && c != '\t'; c = getchar())
s += c;
if (c == EOF)
ans = 0;
}
void read1(char *s)
{
char c = getchar();
int tt = 0;
for (; !isprint(c) || c == ' ' || c == '\n' || c == '\t'; c = getchar())
;
for (; isprint(c) && c != ' ' && c != '\n' && c != '\t'; c = getchar())
s[tt++] = c;
s[tt] = '\0';
if (c == EOF)
ans = 0;
}
template <typename T>
void read1(T &n)
{
T x = 0;
int f = 1;
char c = getchar();
for (; !isdigit(c); c = getchar())
{
if (c == '-')
f = -1;
if (c == EOF)
{
ans = 0;
return;
}
}
for (; isdigit(c); c = getchar())
x = x * 10 + c - 48;
n = x * f;
if (c == EOF)
ans = 0;
if (c != '.')
return;
T l = 0.1;
while ((c = getchar()) <= '9' && c >= '0')
x = x + (c & 15) * l, l *= 0.1;
n = x * f;
if (c == EOF)
ans = 0;
}
void write() {}
void write1(string s)
{
int n = s.size();
for (int i = 0; i < n; i++)
putchar(s[i]);
}
void write1(const char *s)
{
int n = strlen(s);
for (int i = 0; i < n; i++)
putchar(s[i]);
}
void write1(char *s)
{
int n = strlen(s);
for (int i = 0; i < n; i++)
putchar(s[i]);
}
void write1(char s)
{
putchar(s);
}
void write1(float s, int x = 6)
{
char y[10001];
sprintf(y, "%%.%df", x);
printf(y, s);
}
void write1(double s, int x = 6)
{
char y[10001];
sprintf(y, "%%.%dlf", x);
printf(y, s);
}
void write1(long double s, int x = 6)
{
char y[10001];
sprintf(y, "%%.%dLf", x);
printf(y, s);
}
template <typename T>
void write1(T n)
{
if (n < 0)
n = -n, putchar('-');
if (n > 9)
write1(n / 10);
putchar('0' + n % 10);
}
friend ins operator>>(ins x, char *n);
template <typename T>
friend ins operator>>(ins x, T &n);
template <typename T>
friend ins operator<<(ins x, T n);
operator bool()
{
return ans;
}
};
ins operator>>(ins x, char *n)
{
if (!x.ans)
return x;
x.read1(n);
return x;
}
template <typename T>
ins operator>>(ins x, T &n)
{
if (!x.ans)
return x;
x.read1(n);
return x;
}
template <typename T>
ins operator<<(ins x, T n)
{
x.write1(n);
return x;
}
ins yin;
ins yout;
#endif
int n, m;
const int maxn = 1e5 + 10;
vector<int> e[maxn];
int ans = 1, vis[maxn], fd = 0, ff[maxn];
unsigned long long dfs2(int u, int fa)
{
// cerr << u << " " << fa << endl;
unsigned long long hsh = 1;
vis[u] = 1;
vector<unsigned long long> hs;
for (int v : e[u])
if (!vis[v])
hs.push_back(dfs2(v, u));
sort(hs.begin(), hs.end());
for (auto x : hs)
hsh = hsh * 133 + x;
return hsh;
}
void dfs(int u, int fa)
{
ff[u] = fa;
vis[u] = 1;
for (int v : e[u])
if (v != fa)
{
if (vis[v])
{
// cerr << u << " " << v << endl;
for (int i = 1; i <= n; i++)
vis[i] = 0;
int xx = u;
fd = 1;
while (xx != v)
{
vis[xx] = 1;
xx = ff[xx];
}
vis[v] = 1;
xx = u;
unsigned long long nn = 0;
while (xx != v)
{
if (!nn)
nn = dfs2(xx, u);
else
{
auto xxx = dfs2(xx, u);
if (xxx != nn)
{
ans = 0;
return;
}
}
xx = ff[xx];
}
if (nn != dfs2(v, v))
ans = 0;
return;
}
else
dfs(v, u);
if (fd)
return;
}
}
int main()
{
int TTT;
yin >> TTT;
for (int TT = 1; TT <= TTT; TT++)
{
yin >> n >> m;
for (int i = 1; i <= n; i++)
e[i].clear();
for (int i = 1; i <= m; i++)
{
int u, v;
yin >> u >> v;
e[u].push_back(v);
e[v].push_back(u);
}
if (m >= n + 1)
{
if (TT == 39)
assert(0);
puts("NO");
continue;
}
if (m == n - 1)
{
puts("YES");
continue;
}
for (int i = 1; i <= n; i++)
vis[i] = 0;
// cerr << "!!!" << endl;
ans = 1, fd = 0;
dfs(1, 0);
if (ans)
puts("YES");
else
puts("NO");
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 5896kb
input:
4 7 6 1 2 2 3 3 4 4 5 5 6 3 7 3 3 1 2 2 3 3 1 5 5 1 2 2 3 3 4 4 1 1 5 1 0
output:
YES YES NO YES
result:
ok 4 token(s): yes count is 3, no count is 1
Test #2:
score: -100
Wrong Answer
time: 3ms
memory: 6188kb
input:
33192 2 1 1 2 3 2 1 3 2 3 3 3 1 2 1 3 2 3 4 3 1 4 2 4 3 4 4 3 1 3 1 4 2 4 4 4 1 3 1 4 2 4 3 4 4 4 1 3 1 4 2 3 2 4 4 5 1 3 1 4 2 3 2 4 3 4 4 6 1 2 1 3 1 4 2 3 2 4 3 4 5 4 1 5 2 5 3 5 4 5 5 4 1 4 1 5 2 5 3 5 5 5 1 4 1 5 2 5 3 5 4 5 5 5 1 4 1 5 2 4 3 5 4 5 5 5 1 4 1 5 2 4 2 5 3 5 5 6 1 4 1 5 2 4 2 5 3 ...
output:
YES YES YES YES YES NO YES NO NO YES YES NO NO NO NO NO NO YES NO NO NO NO YES NO NO NO NO NO NO NO YES YES NO YES YES NO NO NO NO NO NO NO NO NO YES NO NO NO YES NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO ...
result:
wrong answer expected YES, found NO [39th token]