QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #563312 | #8517. Interesting Paths | qwqwf# | WA | 15ms | 83412kb | C++14 | 1.9kb | 2024-09-14 09:41:49 | 2024-09-14 09:41:53 |
Judging History
answer
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
//#pragma GCC optimize("Ofast","unroll-loops","inline")
#include<bits/stdc++.h>
#define ll long long
//#define int ll
#define pb push_back
#define pii pair<int,int>
#define MP make_pair
#define fi first
#define se second
using namespace std;
const int N=1e6+10,M=1e6+10,mod=998244353;
int n,m,U[N],V[N];
vector<int> G1[N],G2[N];
vector<pii> e[N];
int v1[N],v2[N];
queue<int> q;
bool vis[N],t[N];
bool dfs(int u){
if(u==n) return 1;
if(vis[u]) return 0;
vis[u]=1;
for(pii v:e[u]){
if(dfs(v.fi)) return t[v.se]=1,1;
}
return 0;
}
signed main(){
// freopen("a.in","r",stdin);
// freopen("a.out","w",stdout);
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n>>m;
int ans=0;
v1[1]=1,v2[n]=1;
for(int i=1;i<=m;i++) cin>>U[i]>>V[i],e[U[i]].pb(MP(V[i],i));
if(!dfs(1)) return cout<<0<<'\n',0;
// for(int i=1;i<=m;i++) cout<<t[i]<<' ';cout<<'\n';
for(int i=1,u,v;i<=m;i++) if(t[i]){
u=U[i],v=V[i];
ans+=(v1[u]&&v2[v]);
G1[u].pb(v);
if(v1[u]&&!v1[v]){
q.push(v);
while(!q.empty()){
int x=q.front();q.pop();
if(v1[x]) continue;v1[x]=1;
for(int y:G1[x]) if(!v1[y]) q.push(y);
}
}
G2[v].pb(u);
if(v2[v]&&!v2[u]){
q.push(u);
while(!q.empty()){
int x=q.front();q.pop();
if(v2[x]) continue;v2[x]=1;
for(int y:G2[x]) if(!v2[y]) q.push(y);
}
}
}
for(int i=1,u,v;i<=m;i++) if(!t[i]){
u=U[i],v=V[i];
ans+=(v1[u]&&v2[v]);
G1[u].pb(v);
if(v1[u]&&!v1[v]){
q.push(v);
while(!q.empty()){
int x=q.front();q.pop();
if(v1[x]) continue;v1[x]=1;
for(int y:G1[x]) if(!v1[y]) q.push(y);
}
}
G2[v].pb(u);
if(v2[v]&&!v2[u]){
q.push(u);
while(!q.empty()){
int x=q.front();q.pop();
if(v2[x]) continue;v2[x]=1;
for(int y:G2[x]) if(!v2[y]) q.push(y);
}
}
}
cout<<ans<<'\n';
return 0;
}
/*
5 6
1 2
2 3
1 3
2 5
3 5
3 4
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 7ms
memory: 81452kb
input:
5 7 1 3 3 5 1 2 2 3 3 4 4 5 2 4
output:
4
result:
ok 1 number(s): "4"
Test #2:
score: 0
Accepted
time: 9ms
memory: 83412kb
input:
5 3 1 3 2 3 2 5
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: 0
Accepted
time: 7ms
memory: 79336kb
input:
2 0
output:
0
result:
ok 1 number(s): "0"
Test #4:
score: 0
Accepted
time: 15ms
memory: 81360kb
input:
2 1 1 2
output:
1
result:
ok 1 number(s): "1"
Test #5:
score: 0
Accepted
time: 15ms
memory: 83412kb
input:
10 20 2 8 5 8 4 8 3 10 3 7 2 7 2 5 1 7 6 9 6 10 2 4 5 9 2 10 3 9 7 8 4 10 3 6 2 3 5 7 6 8
output:
0
result:
ok 1 number(s): "0"
Test #6:
score: -100
Wrong Answer
time: 4ms
memory: 81380kb
input:
10 30 8 9 1 5 3 6 4 6 4 7 6 9 3 5 5 6 3 8 1 4 3 4 7 8 2 4 4 5 1 8 6 10 2 10 9 10 1 2 8 10 2 7 2 8 2 5 7 9 2 6 4 8 1 7 1 6 7 10 4 9
output:
18
result:
wrong answer 1st numbers differ - expected: '19', found: '18'