QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#384675#3719. Dynamic GraphppppppWA 114ms4056kbC++171.6kb2024-04-10 09:23:532024-04-10 09:23:53

Judging History

This is the latest submission verdict.

  • [2024-04-10 09:23:53]
  • Judged
  • Verdict: WA
  • Time: 114ms
  • Memory: 4056kb
  • [2024-04-10 09:23:53]
  • Submitted

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;
}

Details

Tip: Click on the bar to expand more detailed information

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'