QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#20106#1825. The King's Guardsconqueror_of_zky#WA 19ms6040kbC++202.5kb2022-02-14 19:27:062022-05-03 09:04:39

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-05-03 09:04:39]
  • 评测
  • 测评结果:WA
  • 用时:19ms
  • 内存:6040kb
  • [2022-02-14 19:27:06]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
struct edge
{
	int u,v,fl,c,n;
}e[500005];
int cnt,head[50005],p[50005],v[50005],s=50001,t=50002,ans,n,m,dep[50005];
inline void add(int u,int v,int w)
{
	e[++cnt]={u,v,0,w,head[u]};
	head[u]=cnt;
	e[++cnt]={v,u,0,0,head[v]};
	head[v]=cnt;
}
inline bool Find()
{
	queue <int> q;
	for(int i=0;i<=t;i++)
		v[i]=dep[i]=0;
	q.push(s);
	v[s]=1;
	dep[s]=1;
	while(!q.empty())
	{
		int x=q.front();
		q.pop();
		for(int i=head[x];i;i=e[i].n)
		{
			if(!v[e[i].v]&&e[i].fl<e[i].c)
			{
				p[e[i].v]=i;
				q.push(e[i].v);
				v[e[i].v]=1;
				dep[e[i].v]=dep[x]+1;
				if(e[i].v==t)
					return 1;
			}
		}
	}
	return 0;
}
inline int dfs(int x,int now)
{
	if(x==t||!now)
		return now;
	int t=now;
	for(int i=head[x];i;i=e[i].n)
	{
		if(e[i].c>e[i].fl&&dep[e[i].v]==dep[x]+1)
		{
            int delta=dfs(e[i].v,min(t,e[i].c-e[i].fl));
			if(!delta)
				dep[e[i].v]=0;
            e[i].fl+=delta;
            e[((i-1)^1)+1].fl-=delta;
            t-=delta;
            if(t==0)
				break;
        }
	}
	return now-t;
}
inline void dinic()
{
	while(Find())
		ans+=dfs(s,1000000007);
}
vector <pair<int,int> > E[1005];
vector <int> ID[1005];
int fa[1005];
inline int ff(int x)
{
	if(fa[x]==x) return x;
	return fa[x]=ff(fa[x]);
}
vector <int> V[1005];
int main(int argc, char** argv) {
	int n,r,g;
	cin >> n >> r >> g;
	int ANS=0;
	for(int i=1;i<=n;i++)
		fa[i]=i;
	for(int i=1;i<=r;i++)
	{
		int u,v,w;
		cin >> u >> v >> w;
		fa[ff(u)]=ff(v);
		ANS+=w; 
		E[w].push_back({u,v});
	}
	int CNT=0;
	for(int i=1;i<=n;i++) CNT+=fa[i]==i;
	int now=n;
	for(int i=1;i<=n;i++)
		add(s,i,1);
	for(int i=1;i<=g;i++)
	{
		int k;
		cin >> k;
		++now;
		for(int j=1;j<=k;j++)
		{
			int x;
			cin >> x;
			V[i].push_back(x);
			add(ff(x),now,1);
		}
		add(now,t,1);
	}
	dinic();
	if(ans!=CNT)
	{
		cout << -1;
		return 0;
	}
	memset(head,0,sizeof head),cnt=0;
	for(int i=1;i<=n;i++)
		add(s,i,1),fa[i]=i;
	for(int i=1;i<=g;i++)
	{
		++now;
		for(auto x:V[i])
			add(x,now,1);
		add(now,t,1);
	}
	dinic();
	if(ans<g)
	{
		cout << -1;
		return 0;
	}
	for(int i=1;i<=1000;i++)
	{
		for(auto x:E[i])
		{
			++now;
			ID[i].push_back(now);
			add(now,t,1);
			add(x.second,now,1);
			add(x.first,now,1);
		}
	}
	dinic();
	if(ans<n)
	{
		cout << -1;
		return 0;
	}
	ANS=0;
	for(int i=1000;i>=1;i--)
	{
		int qwq=0;
		for(auto x:ID[i])
			add(s,x,1),++qwq;
		ans=0;
		dinic();
		ANS+=(qwq-ans)*i;
	}
	cout << ANS;
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 18ms
memory: 6012kb

input:

5 6 2
1 2 1
1 3 4
2 4 2
2 5 5
3 4 7
4 5 3
2 1 2
2 2 4

output:

8

result:

ok answer is '8'

Test #2:

score: 0
Accepted
time: 18ms
memory: 4228kb

input:

10 19 6
1 5 761
6 8 606
3 9 648
2 4 115
5 8 814
1 2 712
4 10 13
5 10 797
3 4 956
1 7 73
5 7 192
2 7 110
5 9 302
3 6 120
6 9 494
1 3 668
3 7 966
6 10 974
3 8 41
2 10 5
3 6 4 3
2 1 7
2 10 8
3 10 7 8
2 2 1

output:

429

result:

ok answer is '429'

Test #3:

score: -100
Wrong Answer
time: 19ms
memory: 6040kb

input:

10 43 3
1 3 656
2 6 856
4 10 99
5 6 900
2 7 766
4 7 582
2 8 135
5 7 831
3 5 12
3 10 789
1 8 66
4 9 390
1 7 238
6 7 960
1 4 624
3 9 602
7 10 366
5 8 526
2 9 561
6 10 722
2 5 904
3 4 35
1 9 768
5 9 457
6 8 61
4 6 192
4 5 96
5 10 747
8 9 611
7 8 953
3 8 449
2 4 228
1 6 197
9 10 160
3 6 869
1 2 785
4 8 ...

output:

523

result:

wrong answer expected '526', found '523'