QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#498839#6121. Hacks With Includescocoa_chan#RE 2ms14008kbC++172.5kb2024-07-30 20:32:222024-07-30 20:32:22

Judging History

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

  • [2024-07-30 20:32:22]
  • 评测
  • 测评结果:RE
  • 用时:2ms
  • 内存:14008kb
  • [2024-07-30 20:32:22]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
struct SCC{
ll t,n,i,m,x,y,b[11000],s;
pair<ll,ll> p[110000],q[110000],c[11000];
vector<ll> v[11000],u[11000],d[11000];
vector<ll>::iterator l;
vector<vector<ll>> ans;
vector<ll> tmp;
void f(ll k)
{
    p[k].first=t;  t++;   b[k]=1;
    vector<ll>::iterator l;
    for(l=v[k].begin();l!=v[k].end();l++)
    {
        if(b[*l]==0)
            f(*l);
    }
    p[k].second=t;  t++;
}
void g(ll k)
{
    d[s].push_back(k);  b[k]=1;
    vector<ll>::iterator l;
    for(l=u[k].begin();l!=u[k].end();l++)
    {
        if(b[*l]==0)
            g(*l);
    }
}
vector<vector<ll>> get_scc(ll N,ll M,vector<pair<ll,ll>> P)
{
    n=N;  m=M;
    for(i=0;i<m;i++)
    {
        x=P[i].first;
        y=P[i].second;
        v[x].push_back(y);
        u[y].push_back(x);
    }
    for(i=1;i<=n;i++)
        sort(v[i].begin(),v[i].end());
    t=1;
    for(i=1;i<=n;i++)
    {
        if(b[i]==0)
            f(i);
    }
    for(i=1;i<=n;i++)
    {
        q[i]={-p[i].second,i};
    }
    sort(q+1,q+n+1);
    for(i=0;i<=n;i++)
        b[i]=0;
    for(i=1;i<=n;i++)
    {
        if(b[q[i].second]==0)
        {
            g(q[i].second);  s++;
        }
    }
    for(i=0;i<s;i++)
        sort(d[i].begin(),d[i].end());
    for(i=0;i<s;i++)
    {
        c[i]={*d[i].begin(),i};
    }
    sort(c,c+s);
    for(i=0;i<s;i++)
    {
        tmp.clear();
        for(l=d[c[i].second].begin();l!=d[c[i].second].end();l++)
            tmp.push_back(*l);
        ans.push_back(tmp);
    }
    return ans;
}
};
SCC scc;
ll n,m,k,i,j,l,r,x,y,z,w,s,t,a[1100000],b[1100000],h[1100000];
vector<vector<ll>> tmp;
pair<ll,ll> p[1100000];
vector<pair<ll,ll>> u;
int main()
{
    scanf("%lld %lld",&n,&m);
    for(i=1;i<=m;i++)
    {
        scanf("%lld %lld",&x,&y);
        p[i]={x,y};
        u.push_back({x,y});
    }
    tmp=scc.get_scc(n,m,u);
    k=tmp.size();
    /*for(i=1;i<=m;i++)
    {
        printf("(%lld):",i);
        for(j=0;j<tmp[i-1].size();j++)
            printf("%lld ",tmp[i-1][j]);
        printf("\n");
    }*/
    for(i=0;i<k;i++)
    {
        for(j=0;j<tmp[i].size();j++)
            b[tmp[i][j]]=i;
    }
    for(i=1;i<=m;i++)
    {
        x=p[i].first;
        y=p[i].second;
        if(b[x]==b[y])
            continue;
        h[b[y]]++;
    }
    for(i=0;i<k;i++)
    {
        if(h[i])
            continue;
        printf("%lld\n",tmp[i][0]);
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 13608kb

input:

4 3
2 1
2 4
3 1

output:

2
3

result:

ok 2 number(s): "2 3"

Test #2:

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

input:

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

output:

3
5

result:

ok 2 number(s): "3 5"

Test #3:

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

input:

9 11
1 3
2 4
2 6
4 1
5 3
5 6
5 8
6 8
7 4
8 1
8 2

output:

5
7
9

result:

ok 3 number(s): "5 7 9"

Test #4:

score: -100
Runtime Error

input:

12963 10384
10844 7220
8829 11517
5915 163
7510 2415
3220 5989
5336 6199
2016 6836
3392 2989
3831 10539
7341 12909
1078 11480
804 3131
9703 9214
3013 11438
6762 5400
4077 10964
1048 12722
7017 8109
5925 10263
6114 633
9567 5897
11842 9331
1975 1407
4556 7087
3816 7081
7078 6136
7646 1703
12242 8557
...

output:


result: