QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#384716#3719. Dynamic GraphppppppAC ✓800ms4096kbC++171.5kb2024-04-10 11:08:482024-04-10 11:08:49

Judging History

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

  • [2024-04-10 11:08:49]
  • 评测
  • 测评结果:AC
  • 用时:800ms
  • 内存:4096kb
  • [2024-04-10 11:08:48]
  • 提交

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