QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#498839 | #6121. Hacks With Includes | cocoa_chan# | RE | 2ms | 14008kb | C++17 | 2.5kb | 2024-07-30 20:32:22 | 2024-07-30 20:32:22 |
Judging History
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]);
}
}
詳細信息
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 ...