QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#384716 | #3719. Dynamic Graph | pppppp | AC ✓ | 800ms | 4096kb | C++17 | 1.5kb | 2024-04-10 11:08:48 | 2024-04-10 11:08:49 |
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<bitset>
#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 ff()
{
bitset<303>op[303];
int hh=0,tt=-1;
for(int i=1;i<=n;i++)
{
if(ru[i]==0)
q[++tt]=i;
mp[i]=ru[i];
op[i][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[x]==0&&st[xx]==0)//都是白色的
op[xx]=op[x]|op[xx];
if(mp[xx]==0)q[++tt]=xx;
}
}
int ans=0;
for(int i=1;i<=n;i++)
{
int tt=op[i].count()-1;//里面1的个数
ans+=tt;
}
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;
if(st[x]==1)st[x]=0;
else st[x]=1;
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: 100
Accepted
time: 800ms
memory: 4096kb
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:
44491 44193 43897 44194 43898 43602 43307 43601 43306 43013 43306 43013 42720 43012 43305 43600 43896 43600 43306 43600 43895 43600 43306 43013 43306 43600 43305 43600 43306 43601 43307 43014 43307 43013 43307 43013 43307 43013 43306 43012 42720 42428 42720 43013 42720 43012 43306 43601 43897 43601 ...
result:
ok 3000 numbers