QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#384675 | #3719. Dynamic Graph | pppppp | WA | 114ms | 4056kb | C++17 | 1.6kb | 2024-04-10 09:23:53 | 2024-04-10 09:23:53 |
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++];
int si=v[x].size();
for(int i=0;i<si;i++)
{
int xx=v[x][i];
mp[xx]--;
if(st[xx]==0)
{
ans+=1;
// kl[xx]+=1;
if(mp[xx]==0)
q[++tt]=xx;
}
}
}
cout<<ans<<endl;
}
void df()
{
while(cin>>n)
{
cin>>m>>k;
for(int i=1;i<=n;i++)
{
v[i].clear();
st[i]=0;
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);
// for(int i=1;i<=n;i++)
// cout<<ru[i]<<" "<<st[i]<<endl;
ff();
}
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t = 1;
// cin >> t;
while (t--) {
df();
}
return 0;
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 114ms
memory: 4056kb
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:
38097 37837 37586 37845 37599 37341 37091 37346 37095 36841 37090 36840 36578 36820 37070 37327 37592 37327 37076 37330 37582 37331 37088 36838 37087 37330 37073 37325 37071 37328 37078 36835 37084 36831 37094 36843 37092 36836 37079 36830 36588 36327 36576 36838 36588 36830 37083 37335 37593 37338 ...
result:
wrong answer 1st numbers differ - expected: '44491', found: '38097'