QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#384685 | #3719. Dynamic Graph | pppppp | WA | 121ms | 4092kb | C++17 | 1.8kb | 2024-04-10 10:04:15 | 2024-04-10 10:04:15 |
Judging History
answer
#include<iostream>
#include<string.h>
#include<stdio.h>
#include<algorithm>
#include<map>
#include<vector>
#include<queue>
#include<stack>
#include<math.h>
#include<set>
#include<unordered_map>
#include<deque>
#define int long long
//__builtin_popcount();
//next_permutation(start,end)和prev_permutation(start,end)
using namespace std;
typedef pair<int, int>PII;
const int N = 3e3+ 10, M = 5e2 + 10;
int n,m,k;
int q[N];
vector<int>v[N];
int ru[N],st[N],mp[N],kl[N];
void dd(int x)
{
if(st[x]==0)
{
st[x]=1;
int si=v[x].size();
for(int i=0;i<si;i++)
{
int tt=v[x][i];
ru[tt]--;
}
}
else
{
st[x]=0;
int si=v[x].size();
for(int i=0;i<si;i++)
{
int tt=v[x][i];
ru[tt]++;
}
}
}
void ff()
{
int ans=0;
int hh=0,tt=-1;
for(int i=1;i<=n;i++)
{
if(st[i]==0&&ru[i]==0)
q[++tt]=i;
mp[i]=ru[i];
kl[i]=1;
}
while(hh<=tt)
{
int x=q[hh++];
// cout<<x<<"[[["< <endl;
int si=v[x].size();
for(int i=0;i<si;i++)
{
int xx=v[x][i];
mp[xx]--;
if(st[xx]==0)
{
if(kl[xx]!=1)kl[xx]=kl[x]+1;//等于前面的
else kl[xx]+=kl[x];
}
if(st[xx]==0&&mp[xx]==0)
{
q[++tt]=xx;
ans+=kl[xx]-1;
// ans+=kl[xx]-1;
}
}
}
// for(int i=1;i<=n;i++)cout<<kl[i]<<" ";
// cout<<endl;
cout<<ans<<endl;
}
void df()
{
while(cin>>n)
{
cin>>m>>k;
for(int i=1;i<=n;i++)
{
v[i].clear();
st[i]=ru[i]=0;
}
for(int i=1;i<=m;i++)
{
int x,y;
cin>>x>>y;
v[x].push_back(y);
ru[y]++;
}
while(k--)
{
int x;
cin>>x;
dd(x);
ff();
}
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t = 1;
// cin >> t;
while (t--) {
df();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 121ms
memory: 4092kb
input:
300 38355 300 169 195 236 244 38 42 205 297 8 50 1 149 170 255 81 123 80 81 78 140 60 88 9 97 253 288 132 170 167 253 18 83 7 32 153 203 4 44 156 159 178 185 2 267 278 297 234 251 50 221 42 222 88 289 130 142 117 254 44 60 120 207 104 167 139 296 175 273 98 253 164 200 23 211 33 260 109 176 17 233 3...
output:
38763 38465 38291 38588 38552 38256 37987 38060 37795 37722 37896 37632 37352 37387 37650 37945 38227 37945 37681 37754 38018 37844 37808 37544 37718 37754 37459 37722 37650 37945 37771 37735 37909 37625 37906 37642 37909 37615 37650 37384 37349 37070 37332 37612 37349 37384 37667 37931 38227 37942 ...
result:
wrong answer 1st numbers differ - expected: '44491', found: '38763'