QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#804900	#9812. Binary Search	ucup-team3723^#	WA	186ms	44344kb	C++14	2.8kb	2024-12-08 09:58:45	2024-12-08 09:58:45

Judging History

This is the latest submission verdict.

[2024-12-08 09:58:45]
Judged

Verdict: WA
Time: 186ms
Memory: 44344kb

Show

[2024-12-08 09:58:45]
Submitted

answer

#include <bits/stdc++.h>
#define dbg(x) cerr << #x << ':'<< (x) << endl;
#define ALL(x) x.begin(),x.end()
using namespace std;
using ll = long long;
using ld = long double;

int main()
{
    int n,m;
    cin >> n >> m;

    vector<int> s(n);
    for (int i = 0; i < n; i++) cin >> s[i];

    vector<vector<vector<int>>> g(2,vector<vector<int>>(n));
    for (int i = 0; i < m; i++) {
        int u,v;
        cin >> u >> v;
        --u;--v;
        g[s[v]][u].emplace_back(v);
        g[s[u]][v].emplace_back(u);
    }

    // infinityの判定
    vector<bool> used(n);
    queue<int> que;
    vector<vector<int>> cnt(2,vector<int>(n));
    for (int i = 0; i < n; i++) {
        if (g[0][i].empty() || g[1][i].empty()) {
            used[i] = true;
            que.push(i);
        }
        cnt[0][i] = g[0][i].size();
        cnt[1][i] = g[1][i].size();
    }

    while (!que.empty()) {
        int x = que.front();
        que.pop();

        for (int y : g[0][x]) {
            --cnt[s[x]][y];
            if (!used[y] && cnt[s[x]][y] == 0) {
                used[y] = true;
                que.push(y);
            }
        }
        for (int y : g[1][x]) {
            --cnt[s[x]][y];
            if (!used[y] && cnt[s[x]][y] == 0) {
                used[y] = true;
                que.push(y);
            }
        }
    }
    bool infinity_flag = false;
    for (int i = 0; i < n; i++) {
        if (!used[i]) {
            infinity_flag = true;
        }
    }

    if (infinity_flag) {
       cout << "infinity" << endl;
       return 0;
    }

    int ans = INT_MAX;
    for (int i = 0; i < 4; i++) {
        vector<vector<int>> dis(2,vector<int>(n,0));
        queue<pair<int,int>> q;
        for (int j = 0; j < n; j++) {
            if (s[j] == (i&1)) {
                dis[i>>1][j] = 1;
                q.push({i>>1,j});
            }
        }

        bool inf_flag = false;
        while (!q.empty()) {
            auto [num,x] = q.front();
            q.pop();
            // cerr << "s:" << num << ' ' << x << endl;

            for (int y : g[1-num][x]) {
                if (dis[s[x]][y] != 0) {
                    // if (dis[s[x]][y] != dis[num][x]+1) inf_flag = true;
                    continue;
                }
                // cerr << "t:" << s[x] << ' ' << y << endl;
                dis[s[x]][y] = dis[num][x]+1;
                q.push({s[x],y});
            }
            if (inf_flag) break;
        }

        int tmp = 0;
        for (int j = 0; j < 2; j++) for (int k = 0; k < n; k++) tmp = max(tmp,dis[j][k]);
        if (!inf_flag) ans = min(ans, tmp+1);
    }
    
    // if (ans == INT_MAX) cout << "infinity" << endl;
    // else cout << ans << endl;
    cout << ans << endl;

    return 0;
}

源文件, 语言: C++14

詳細信息

Test #1:

score: 100

Accepted

time: 0ms

memory: 3740kb

input:

output:

result:

ok single line: '4'

Test #2:

score: 0

Accepted

time: 0ms

memory: 3612kb

input:

6 7
0 0 1 1 0 1
1 2
3 1
1 4
2 3
4 2
3 4
5 6

output:

infinity

result:

ok single line: 'infinity'

Test #3:

score: 0

Accepted

time: 0ms

memory: 3528kb

input:

1 0
0

output:

result:

ok single line: '1'

Test #4:

score: 0

Accepted

time: 0ms

memory: 3584kb

input:

1 0
1

output:

result:

ok single line: '1'

Test #5:

score: 0

Accepted

time: 1ms

memory: 3608kb

input:

2 0
1 1

output:

result:

ok single line: '1'

Test #6:

score: 0

Accepted

time: 0ms

memory: 3520kb

input:

2 0
1 0

output:

result:

ok single line: '2'

Test #7:

score: 0

Accepted

time: 0ms

memory: 3476kb

input:

2 1
0 0
1 2

output:

result:

ok single line: '1'

Test #8:

score: 0

Accepted

time: 0ms

memory: 3468kb

input:

2 1
0 1
2 1

output:

result:

ok single line: '2'

Test #9:

score: 0

Accepted

time: 0ms

memory: 3804kb

input:

output:

result:

ok single line: '2'

Test #10:

score: 0

Accepted

time: 0ms

memory: 3588kb

input:

output:

result:

ok single line: '1'

Test #11:

score: 0

Accepted

time: 0ms

memory: 3468kb

input:

output:

result:

ok single line: '1'

Test #12:

score: 0

Accepted

time: 0ms

memory: 3496kb

input:

output:

result:

ok single line: '2'

Test #13:

score: 0

Accepted

time: 0ms

memory: 3700kb

input:

output:

result:

ok single line: '4'

Test #14:

score: 0

Accepted

time: 0ms

memory: 3544kb

input:

output:

infinity

result:

ok single line: 'infinity'

Test #15:

score: 0

Accepted

time: 0ms

memory: 3468kb

input:

output:

result:

ok single line: '2'

Test #16:

score: 0

Accepted

time: 0ms

memory: 3552kb

input:

3 1
0 0 1
1 2

output:

result:

ok single line: '2'

Test #17:

score: 0

Accepted

time: 0ms

memory: 3584kb

input:

3 1
1 0 1
1 3

output:

result:

ok single line: '2'

Test #18:

score: 0

Accepted

time: 0ms

memory: 3588kb

input:

3 1
0 1 1
1 2

output:

result:

ok single line: '2'

Test #19:

score: 0

Accepted

time: 0ms

memory: 3612kb

input:

output:

result:

ok single line: '2'

Test #20:

score: 0

Accepted

time: 0ms

memory: 3584kb

input:

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

output:

result:

ok single line: '3'

Test #21:

score: 0

Accepted

time: 0ms

memory: 3556kb

input:

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

output:

result:

ok single line: '4'

Test #22:

score: 0

Accepted

time: 0ms

memory: 3536kb

input:

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

output:

result:

ok single line: '2'

Test #23:

score: 0

Accepted

time: 0ms

memory: 3764kb

input:

output:

result:

ok single line: '2'

Test #24:

score: 0

Accepted

time: 0ms

memory: 3588kb

input:

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

output:

result:

ok single line: '4'

Test #25:

score: 0

Accepted

time: 0ms

memory: 3764kb

input:

output:

result:

ok single line: '2'

Test #26:

score: 0

Accepted

time: 0ms

memory: 3740kb

input:

3 1
0 1 1
1 3

output:

result:

ok single line: '2'

Test #27:

score: 0

Accepted

time: 0ms

memory: 3592kb

input:

7 18
0 0 0 0 1 1 0
4 2
7 1
2 3
7 2
6 5
4 1
5 7
6 3
6 1
6 7
4 7
5 1
5 3
4 5
3 7
4 6
2 1
2 5

output:

infinity

result:

ok single line: 'infinity'

Test #28:

score: 0

Accepted

time: 0ms

memory: 3744kb

input:

7 17
1 0 1 0 0 0 0
6 3
5 1
6 4
7 6
7 2
3 1
6 1
2 4
1 2
4 7
7 1
3 2
5 2
4 5
5 7
3 7
3 4

output:

infinity

result:

ok single line: 'infinity'

Test #29:

score: 0

Accepted

time: 0ms

memory: 3596kb

input:

output:

infinity

result:

ok single line: 'infinity'

Test #30:

score: 0

Accepted

time: 0ms

memory: 3540kb

input:

8 14
1 0 0 0 1 1 1 0
2 4
8 4
2 1
5 6
8 1
3 7
7 5
7 4
3 4
1 5
2 3
8 3
5 3
7 2

output:

infinity

result:

ok single line: 'infinity'

Test #31:

score: 0

Accepted

time: 0ms

memory: 3584kb

input:

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

output:

result:

ok single line: '2'

Test #32:

score: 0

Accepted

time: 0ms

memory: 3468kb

input:

8 17
0 0 1 0 1 0 0 1
1 4
7 8
8 5
1 7
1 2
8 4
6 1
5 6
8 2
6 4
5 3
5 4
6 7
1 5
2 3
6 8
7 2

output:

infinity

result:

ok single line: 'infinity'

Test #33:

score: 0

Accepted

time: 0ms

memory: 3540kb

input:

output:

result:

ok single line: '2'

Test #34:

score: 0

Accepted

time: 0ms

memory: 3592kb

input:

2 1
1 0
1 2

output:

result:

ok single line: '2'

Test #35:

score: 0

Accepted

time: 0ms

memory: 3476kb

input:

output:

infinity

result:

ok single line: 'infinity'

Test #36:

score: 0

Accepted

time: 0ms

memory: 3476kb

input:

7 20
0 1 0 1 1 1 0
7 5
2 7
2 1
1 4
5 3
2 3
4 5
1 7
6 4
4 3
6 7
2 6
3 1
7 3
4 2
7 4
3 6
1 6
5 6
5 1

output:

infinity

result:

ok single line: 'infinity'

Test #37:

score: 0

Accepted

time: 0ms

memory: 3740kb

input:

2 1
1 0
2 1

output:

result:

ok single line: '2'

Test #38:

score: 0

Accepted

time: 0ms

memory: 3536kb

input:

7 7
1 1 1 1 0 1 1
1 6
7 5
2 4
3 6
4 5
6 4
1 4

output:

result:

ok single line: '2'

Test #39:

score: 0

Accepted

time: 0ms

memory: 3476kb

input:

2 1
0 0
2 1

output:

result:

ok single line: '1'

Test #40:

score: 0

Accepted

time: 0ms

memory: 3588kb

input:

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

output:

infinity

result:

ok single line: 'infinity'

Test #41:

score: 0

Accepted

time: 0ms

memory: 3760kb

input:

9 3
0 1 1 1 1 1 1 1 0
1 7
1 8
9 8

output:

result:

ok single line: '2'

Test #42:

score: 0

Accepted

time: 0ms

memory: 3584kb

input:

output:

result:

ok single line: '1'

Test #43:

score: 0

Accepted

time: 20ms

memory: 11300kb

input:

95705 24453
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

output:

result:

ok single line: '2'

Test #44:

score: -100

Wrong Answer

time: 186ms

memory: 44344kb

input:

300000 299999
0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 ...

output:

result:

wrong answer 1st lines differ - expected: '300000', found: '5'