QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#384685#3719. Dynamic GraphppppppWA 121ms4092kbC++171.8kb2024-04-10 10:04:152024-04-10 10:04:15

Judging History

This is the latest submission verdict.

  • [2024-04-10 10:04:15]
  • Judged
  • Verdict: WA
  • Time: 121ms
  • Memory: 4092kb
  • [2024-04-10 10:04:15]
  • 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++];
//		cout<<x<<"[[["< <endl; 
		int si=v[x].size();
		for(int i=0;i<si;i++)
		{
			int xx=v[x][i];
			mp[xx]--;
			if(st[xx]==0) 
			{
				if(kl[xx]!=1)kl[xx]=kl[x]+1;//等于前面的 
				else kl[xx]+=kl[x];
				
			}
			if(st[xx]==0&&mp[xx]==0)
			{
				q[++tt]=xx;
				ans+=kl[xx]-1;
//				ans+=kl[xx]-1;
			}
		}
	}
//	for(int i=1;i<=n;i++)cout<<kl[i]<<" ";
//	cout<<endl;
	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;
			dd(x);
			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: 121ms
memory: 4092kb

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:

38763
38465
38291
38588
38552
38256
37987
38060
37795
37722
37896
37632
37352
37387
37650
37945
38227
37945
37681
37754
38018
37844
37808
37544
37718
37754
37459
37722
37650
37945
37771
37735
37909
37625
37906
37642
37909
37615
37650
37384
37349
37070
37332
37612
37349
37384
37667
37931
38227
37942
...

result:

wrong answer 1st numbers differ - expected: '44491', found: '38763'