QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#375006#3719. Dynamic Graphucup-team1251AC ✓315ms24648kbC++171.2kb2024-04-02 20:45:282024-04-02 20:45:30

Judging History

你现在查看的是最新测评结果

  • [2024-04-02 20:45:30]
  • 评测
  • 测评结果:AC
  • 用时:315ms
  • 内存:24648kb
  • [2024-04-02 20:45:28]
  • 提交

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