QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#500701#6536. Lawyerscocoa_chan#ML 2ms12084kbC++171.1kb2024-08-01 18:12:502024-08-01 18:12:56

Judging History

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

  • [2024-08-01 18:12:56]
  • 评测
  • 测评结果:ML
  • 用时:2ms
  • 内存:12084kb
  • [2024-08-01 18:12:50]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef int ll;
ll n,m,i,j,k,l,r,x,y,z,w,s,t,a[220000],b[220000],ok[220000],chk[220000];
vector<ll> v[220000];
pair<ll,ll> p[220000];
set<pair<ll,ll>> st;
ll f(ll x,ll y)
{
    chk[x]=1;
    ll i,s=ok[x];
    for(i=0;i<v[x].size();i++)
    {
        if(v[x][i]==y)
            continue;
        s|=f(v[x][i],x);
    }
    return s;
}
int main()
{
    scanf("%d %d",&n,&m);
    for(i=1;i<=m;i++)
    {
        scanf("%d %d",&x,&y);
        p[i]={x,y};
        //u.push_back(p[i]);
        //mp[p[i]]=1;
        st.insert(p[i]);
    }
    //sort(u.begin(),u.end());
    for(i=1;i<=m;i++)
    {
        if(st.find({p[i].second,p[i].first})==st.end())
            {
                ok[p[i].second]=1;
            }
        else
        {
            v[p[i].first].push_back(p[i].second);
        }
    }
    for(i=1;i<=n;i++)
    {
        if(chk[i]==0)
        {
            if(!f(i,0))
            {
                printf("NO");
                return 0;
            }
        }
    }
    printf("YES");
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3 3
1 2
2 3
3 1

output:

YES

result:

ok answer is YES

Test #2:

score: 0
Accepted
time: 0ms
memory: 11888kb

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: 9956kb

input:

4 4
1 2
2 1
3 4
4 3

output:

NO

result:

ok answer is NO

Test #4:

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

input:

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

output:

NO

result:

ok answer is NO

Test #5:

score: 0
Accepted
time: 0ms
memory: 12080kb

input:

4 7
1 2
2 1
1 3
3 1
1 4
4 1
2 4

output:

YES

result:

ok answer is YES

Test #6:

score: -100
Memory Limit Exceeded

input:

5 12
2 4
3 1
3 4
1 2
4 2
2 3
5 4
1 3
1 4
4 1
3 2
4 3

output:


result: