QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#375006 | #3719. Dynamic Graph | ucup-team1251 | AC ✓ | 315ms | 24648kb | C++17 | 1.2kb | 2024-04-02 20:45:28 | 2024-04-02 20:45:30 |
Judging History
answer
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int>PII;
typedef pair<string,string>PSS;
const int N=3e5+5;
int dep[N],fa[N][31];
vector<int>E[N],E1[N];
set<int>s;
int pr[N];
int din[N],din1[N];
int c[N];
map<PII,int>mp;
bitset<305>A[305];
int tuop(int n)
{
bitset<305>B[305];
int ans=0;
queue<int>q;
for(int i=1;i<=n;i++)
{
B[i]=A[i];
din1[i]=din[i];
if(din1[i]==0)
{
q.push(i);
}
}
while(q.size()!=0)
{
int u=q.front();
q.pop();
if(B[u].any()!=false)
{
ans+=B[u].count()-1;
}
for(auto v:E[u])
{
if(--din1[v]==0)
{
q.push(v);
}
if(B[v].any()==false)continue;
B[v]=B[u]|B[v];
}
}
return ans;
}
void solve()
{
int n,m,q;
while(cin>>n>>m>>q)
{
for(int i=1;i<=n;i++)
{
A[i].reset();
A[i].set(i-1);
}
for(int i=1;i<=m;i++)
{
int u,v;
cin>>u>>v;
E[v].push_back(u);
din[u]++;
}
while(q--)
{
int x;
cin>>x;
A[x].flip(x-1);
// cout<<A[x]<<"\n";
int ans=tuop(n);
// cout<<ans<<"\n";
cout<<ans<<"\n\n";
}
for(int i=1;i<=n;i++)E[i].clear(),din[i]=0;
}
}
signed main()
{
// ios_base::sync_with_stdio(false);
// cin.tie(nullptr);
// cout.tie(nullptr);
int t=1;
// cin>>t;
while(t--){
solve();
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 315ms
memory: 24648kb
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 ...
result:
ok 3000 numbers