QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#201084 | #6536. Lawyers | ucup-team1209# | WA | 2ms | 10676kb | C++20 | 1.4kb | 2023-10-05 10:22:47 | 2023-10-05 10:22:48 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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