NOI.AC

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#214938	#3857. 同构	18112606231	100	2985ms	64688kb	C++11	3.1kb	2024-11-24 10:59:39	2024-11-24 13:15:27

answer

#include <bits/stdc++.h>
#define int long long
using namespace std;
int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}
int n, m, u, v, t, belong[1000001], val[3][1000001], color[3][1000001], ys[2], head[2000001], pos;
struct edge
{
    int u, v, next;
} e[2000001];
void add(int u, int v)
{
    e[++pos] = {u, v, head[u]};
    head[u] = pos;
}
vector<int> xhval[2], colorval[2][2];
char s[1000001];
bool flag, ans;
void dfs(int u, int st)
{
    if (belong[u] != -1)
    {
        if (belong[u] != st)
        {
            flag = false;
        }
        return;
    }
    belong[u] = st;
    for (int i = 0; i <= 1; i++)
    {
        xhval[i].push_back(val[i][u]);
        colorval[i][st ^ color[i][u]].push_back(val[i][u]);
        ys[i] += color[i][u];
    }
    for (int i = head[u]; i; i = e[i].next)
    {
        int v = e[i].v;
        dfs(v, st ^ 1);
    }
}
void init()
{
    for (int i = 1; i <= pos; i++)
    {
        e[i].u = 0;
        e[i].v = 0;
        e[i].next = 0;
    }
    for (int i = 1; i <= n; i++)
    {
        head[i] = 0;
        belong[i] = -1;
    }
    pos = 0;
}
signed main()
{
    t = read();
    while (t--)
    {
        n = read();
        m = read();
        init();
        for (int i = 1; i <= m; i++)
        {
            u = read();
            v = read();
            add(u, v);
            add(v, u);
        }
        for (int i = 0; i <= 1; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                val[i][j] = read();
            }
            scanf("%s", s + 1);
            for (int j = 1; j <= n; j++)
            {
                if (s[j] == 'R')
                    color[i][j] = 1;
                else
                    color[i][j] = 0;
            }
        }
        ans = true;
        for (int i = 1; i <= n; i++)
        {
            if (belong[i] == -1)
            {
                flag = true;
                for (int j = 0; j <= 1; j++)
                {
                    xhval[j].clear();
                    colorval[j][0].clear();
                    colorval[j][1].clear();
                }
                ys[0] = ys[1] = 0;
                dfs(i, 0);
                for (int j = 0; j <= 1; j++)
                {
                    sort(xhval[j].begin(), xhval[j].end());
                    sort(colorval[j][0].begin(), colorval[j][0].end());
                    sort(colorval[j][1].begin(), colorval[j][1].end());
                }
                if ((xhval[0] != xhval[1]) || (flag && (colorval[0][0] != colorval[1][0] || colorval[0][1] != colorval[1][1])) || (!flag && abs(ys[1] - ys[0]) % 2 != 0))
                {
                    ans = false;
                }
            }
        }
        puts(ans ? "YES" : "NO");
    }
    return 0;
}

源文件, 语言: C++11

详细

小提示：点击横条可展开更详细的信息

Test #1:

score: 10

Accepted

time: 0ms

memory: 3308kb

input:

100
5 10
2 1
2 5
2 4
2 3
1 5
1 4
1 3
5 4
5 3
4 3
13 13 13 5 13
RRBBB
13 5 13 13 13
RRBRR
5 7
1 2
1 5...

output:

YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
NO
NO
YES
YES
NO
NO
NO
YES
YES
YES
NO
YES
YES
NO
YES
YES
...

result:

ok 100 tokens

Test #2:

score: 10

Accepted

time: 0ms

memory: 5348kb

input:

100
5 10
2 1
2 5
2 4
2 3
1 5
1 4
1 3
5 4
5 3
4 3
13 13 13 5 13
RRBBB
13 5 13 13 13
RRBRR
5 7
1 2
1 5...

output:

YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
NO
NO
YES
YES
NO
NO
NO
YES
YES
YES
NO
YES
YES
NO
YES
YES
...

result:

ok 100 tokens

Test #3:

score: 10

Accepted

time: 624ms

memory: 64688kb

input:

5011
10 6
4 6
9 1
1 5
10 8
8 2
2 7
11757654 864071248 323229178 555908143 641822091 26217619 5962598...

output:

NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
N...

result:

ok 5011 tokens

Test #4:

score: 10

Accepted

time: 625ms

memory: 60792kb

input:

5011
10 5
9 2
2 4
10 6
3 8
8 5
522954355 997994823 387111720 263319934 982267698 414817746 206986255...

output:

NO
NO
NO
NO
NO
NO
NO
NO
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
...

result:

ok 5011 tokens

Test #5:

score: 10

Accepted

time: 292ms

memory: 14436kb

input:

5010
10 10
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
1 3
208620692 818588673 934944057 995455769 12467498...

output:

NO
NO
NO
NO
NO
NO
YES
NO
NO
YES
YES
NO
NO
YES
YES
NO
NO
NO
YES
NO
NO
NO
NO
YES
NO
YES
NO
YES
NO
NO
N...

result:

ok 5010 tokens

Test #6:

score: 10

Accepted

time: 262ms

memory: 14368kb

input:

5010
10 10
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
1 3
236429395 288287881 503399349 845206307 89186299...

output:

YES
NO
NO
NO
NO
NO
YES
NO
YES
NO
NO
NO
NO
NO
NO
NO
YES
NO
YES
NO
YES
YES
NO
NO
NO
NO
YES
YES
NO
NO
N...

result:

ok 5010 tokens

Test #7:

score: 10

Accepted

time: 290ms

memory: 14336kb

input:

5010
10 10
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
1 3
503181870 30925372 20463156 179388247 123477103 ...

output:

YES
NO
NO
NO
NO
NO
YES
NO
YES
NO
NO
NO
YES
NO
NO
YES
NO
YES
NO
NO
NO
NO
YES
YES
NO
NO
NO
NO
NO
YES
N...

result:

ok 5010 tokens

Test #8:

score: 10

Accepted

time: 296ms

memory: 38816kb

input:

25054
5 10
4 5
4 2
4 3
4 1
5 2
5 3
5 1
2 3
2 1
3 1
12 2 9 10 7
RRRBB
10 2 9 7 12
RRBRB
1 0
4
R
4
R
8...

output:

YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
NO
YES
NO
NO
YES
YES
YES
NO
YES
NO
YES
YES
NO
YES
YES
NO
...

result:

ok 25054 tokens

Test #9:

score: 10

Accepted

time: 343ms

memory: 31168kb

input:

output:

YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO...

result:

ok 25174 tokens

Test #10:

score: 10

Accepted

time: 253ms

memory: 37084kb

input:

output:

YES
YES
YES
NO
YES
YES
NO
NO
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
Y...

result:

ok 25047 tokens

Extra Test:

score: 0

Extra Test Passed