QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#201084#6536. Lawyersucup-team1209#WA 2ms10676kbC++201.4kb2023-10-05 10:22:472023-10-05 10:22:48

Judging History

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

  • [2023-10-05 10:22:48]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:10676kb
  • [2023-10-05 10:22:47]
  • 提交

answer

#include <bits/stdc++.h>
#define cs const
#define pb push_back
using namespace std;

cs int N = 2e5 + 5; 

int n, m;
vector <int> e[N];
int dfn[N], low[N], ind; 
int stk[N], top, in[N];
int bel[N], cnt, num[N];

void dfs(int x) {
    dfn[x] = low[x] = ++ ind; 
    stk[++ top] = x; 
    in[x] = 1;     
    for(int v : e[x]) {
        if(!dfn[v]) {
            dfs(v), low[x] = min(low[x], low[v]);
        }
        else if(in[v]) low[x] = min(low[x], dfn[v]);
    }
    if(low[x] == dfn[x]) {
        int y; ++ cnt; 
        do {
            y = stk[top];
            -- top; 
            in[y] = 0; 
            bel[y] = cnt;
            num[cnt] ++; 
        } while(y != x);
    }
}

int main() {
    #ifdef zqj
    freopen("1.in","r",stdin);
    #endif
    cin >> n >> m;
    for(int i = 1; i <= m; i++) {
        int u, v; 
        scanf("%d%d", &u, &v);
        e[u].pb(v);
    }
    for(int i = 1;i <= n; i++) {
        if(!dfn[i]) dfs(i);
    }
    vector <int> d(cnt + 1);
    for(int i = 1; i <= n; i++) {
        for(int v : e[i]) {
            if(bel[v] != bel[i]) {
                ++ d[bel[v]];
            }
        }
    }
    for(int i = 1;i <= cnt; i++) {
        if(d[i] == 0) {
            if(num[i] <= 2) {
                cout << "NO\n";
                return 0; 
            }
        }
    }
    cout << "YES" << '\n';
    return 0; 
}

详细

Test #1:

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

input:

3 3
1 2
2 3
3 1

output:

YES

result:

ok answer is YES

Test #2:

score: 0
Accepted
time: 2ms
memory: 9164kb

input:

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

output:

NO

result:

ok answer is NO

Test #3:

score: 0
Accepted
time: 2ms
memory: 9360kb

input:

4 4
1 2
2 1
3 4
4 3

output:

NO

result:

ok answer is NO

Test #4:

score: -100
Wrong Answer
time: 2ms
memory: 10640kb

input:

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

output:

YES

result:

wrong answer expected NO, found YES