QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#24221#1825. The King's Guardsp_b_p_bWA 547ms16504kbC++174.0kb2022-03-27 20:10:092022-04-30 05:16:19

Judging History

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

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

answer

#include<bits/stdc++.h>
namespace my_std{
	using namespace std;
	#define pii pair<int,int>
	#define fir first
	#define sec second
	#define MP make_pair
	#define rep(i,x,y) for (int i=(x);i<=(y);i++)
	#define drep(i,x,y) for (int i=(x);i>=(y);i--)
	#define go(x) for (int i=head[x];i;i=edge[i].nxt)
	#define templ template<typename T>
	typedef long long ll;
	typedef double db;
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	templ inline T rnd(T l,T r) {return uniform_int_distribution<T>(l,r)(rng);}
	templ inline bool chkmax(T &x,T y){return x<y?x=y,1:0;}
	templ inline bool chkmin(T &x,T y){return x>y?x=y,1:0;}
	templ inline void read(T& t)
	{
		t=0;char f=0,ch=getchar();double d=0.1;
		while(ch>'9'||ch<'0') f|=(ch=='-'),ch=getchar();
		while(ch<='9'&&ch>='0') t=t*10+ch-48,ch=getchar();
		if(ch=='.'){ch=getchar();while(ch<='9'&&ch>='0') t+=d*(ch^48),d*=0.1,ch=getchar();}
		t=(f?-t:t);
	}
	template<typename T,typename... Args>inline void read(T& t,Args&... args){read(t); read(args...);}
	char __sr[1<<21],__z[20];int __C=-1,__zz=0;
	inline void Ot(){fwrite(__sr,1,__C+1,stdout),__C=-1;}
	inline void print(int x)
	{
		if(__C>1<<20)Ot();if(x<0)__sr[++__C]='-',x=-x;
		while(__z[++__zz]=x%10+48,x/=10);
		while(__sr[++__C]=__z[__zz],--__zz);__sr[++__C]='\n';
	}
	void file()
	{
		#ifdef NTFOrz
		freopen("a.in","r",stdin);
		#endif
	}
	inline void chktime()
	{
		#ifdef NTFOrz
		cerr<<clock()/1000.0<<'\n';
		#endif
	}
	#ifdef mod
	ll ksm(ll x,int y){ll ret=1;for (;y;y>>=1,x=x*x%mod) if (y&1) ret=ret*x%mod;return ret;}
	ll inv(ll x){return ksm(x,mod-2);}
	#else
	ll ksm(ll x,int y){ll ret=1;for (;y;y>>=1,x=x*x) if (y&1) ret=ret*x;return ret;}
	#endif
//	inline ll mul(ll a,ll b){ll d=(ll)(a*(double)b/mod+0.5);ll ret=a*b-d*mod;if (ret<0) ret+=mod;return ret;}
}
using namespace my_std;

namespace Flow
{
	#define sz 505050
	int n,S,T;
	struct hh{int t,w,c,nxt;}edge[sz<<1];
	int head[sz],ecnt=1;
	void make_edge(int f,int t,int w,int c) 
	{
		c=-c;
		edge[++ecnt]=(hh){t,w,c,head[f]};
		head[f]=ecnt;
		edge[++ecnt]=(hh){f,0,-c,head[t]};
		head[t]=ecnt; 
	}
	
	int dis[sz],flow[sz];
	int pre[sz];
	bool in[sz];
	bool SPFA()
	{
		rep(i,1,n) dis[i]=1e9,flow[i]=0,pre[i]=0;
		queue<int>q;
		q.push(S);dis[S]=0;flow[S]=1e9;in[S]=1;
		#define v edge[i].t
		while (!q.empty())
		{
			int x=q.front();q.pop();in[x]=0;
			go(x) 
				if (edge[i].w&&chkmin(dis[v],dis[x]+edge[i].c))  
					flow[v]=min(flow[x],edge[i].w),pre[v]=i,(!in[v]&&(q.push(v),0)),in[v]=1;
		}
		#undef v
		return dis[T]!=1e9;
	}
	int mxflow,mncost;
	void update(){int f=flow[T];mxflow+=f;mncost+=dis[T]*f;for (int x=T,i;i=pre[x],x!=S;x=edge[i^1].t) edge[i].w-=f,edge[i^1].w+=f;}
	int work(){while (SPFA()) update();return -mncost;}
	#undef sz
}

namespace Build
{
	#define sz 333
	int n,m,K;
	int S,T;
	struct hh{int u,v,w;bool operator < (const hh &a) const {return w<a.w;}}e[sz*sz];
	int fa[sz];
	int getfa(int x){return x==fa[x]?x:fa[x]=getfa(fa[x]);}
	vector<int>V[sz];
	
	void dfs(int x,int f)
	{
		Flow::make_edge(x*2-1,x*2,1,0);
		for (auto ee:V[x])
		{
			int v=e[ee].u^e[ee].v^x; if (v==f) continue;
			Flow::make_edge(v*2,x*2-1,1,0);
			Flow::make_edge(v*2,T,1,e[ee].w);
			dfs(v,x);
		}
	}
	
	void work()
	{
		read(n,m,K);
		S=n*2+K+1,T=S+1;
		int x,y,z;
		rep(i,1,m) read(x,y,z),e[i]=(hh){x,y,z};
		sort(e+1,e+m+1);
		rep(i,1,n) fa[i]=i;
		ll ans=0;
		rep(i,1,m)
		{
			x=e[i].u,y=e[i].v;
			if (getfa(x)!=getfa(y)) V[x].push_back(i),V[y].push_back(i),fa[fa[x]]=fa[y],ans+=e[i].w;
		}
		const int MX=333333; int c=0;
		rep(i,1,n) if (i==fa[i]) dfs(i,0),Flow::make_edge(i*2,T,1,MX),++c;
		rep(i,1,K)
		{
			Flow::make_edge(S,n*2+i,1,0);
			int k; read(k);
			while (k--) read(x),Flow::make_edge(n*2+i,x*2-1,1,0);
		}
		Flow::n=Flow::T=T; Flow::S=S;
		ans-=Flow::work();
		ans+=c*MX;
		if (Flow::mxflow==K) cout<<ans<<'\n';
		else puts("-1");
	}
}

int main()
{
	file();
	Build::work();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 13904kb

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: 2ms
memory: 15916kb

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: 0
Accepted
time: 0ms
memory: 16016kb

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:

526

result:

ok answer is '526'

Test #4:

score: 0
Accepted
time: 3ms
memory: 14000kb

input:

277 9038 1
226 260 740
44 226 376
151 263 611
67 269 241
120 181 677
259 271 782
37 52 310
48 152 452
168 266 823
85 234 100
46 201 738
129 153 301
69 147 434
13 72 764
13 234 316
171 222 398
214 255 21
112 158 430
20 118 407
45 152 971
205 214 272
221 275 362
198 268 472
117 176 207
31 75 652
139 1...

output:

5375

result:

ok answer is '5375'

Test #5:

score: 0
Accepted
time: 13ms
memory: 15956kb

input:

297 27966 132
15 197 980
226 259 950
161 168 142
118 176 834
157 221 806
24 210 432
212 242 838
110 166 177
78 170 801
52 166 3
89 213 448
45 170 626
250 251 268
93 222 679
7 128 839
5 7 320
132 191 1
192 295 717
36 231 542
162 175 508
173 178 458
211 272 926
46 168 145
19 150 805
165 262 198
50 179...

output:

775

result:

ok answer is '775'

Test #6:

score: 0
Accepted
time: 6ms
memory: 15936kb

input:

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

output:

17

result:

ok answer is '17'

Test #7:

score: 0
Accepted
time: 209ms
memory: 16504kb

input:

300 44850 299
1 2 1
1 3 1
1 4 1
1 5 1
1 6 1
1 7 1
1 8 1
1 9 1
1 10 1
1 11 1
1 12 1
1 13 1
1 14 1
1 15 1
1 16 1
1 17 1
1 18 1
1 19 1
1 20 1
1 21 1
1 22 1
1 23 1
1 24 1
1 25 1
1 26 1
1 27 1
1 28 1
1 29 1
1 30 1
1 31 1
1 32 1
1 33 1
1 34 1
1 35 1
1 36 1
1 37 1
1 38 1
1 39 1
1 40 1
1 41 1
1 42 1
1 43 1
...

output:

1000

result:

ok answer is '1000'

Test #8:

score: 0
Accepted
time: 547ms
memory: 16484kb

input:

300 44850 299
1 2 1
1 3 1
1 4 1
1 5 1
1 6 1
1 7 1
1 8 1
1 9 1
1 10 1
1 11 1
1 12 1
1 13 1
1 14 1
1 15 1
1 16 1
1 17 1
1 18 1
1 19 1
1 20 1
1 21 1
1 22 1
1 23 1
1 24 1
1 25 1
1 26 1
1 27 1
1 28 1
1 29 1
1 30 1
1 31 1
1 32 1
1 33 1
1 34 1
1 35 1
1 36 1
1 37 1
1 38 1
1 39 1
1 40 1
1 41 1
1 42 1
1 43 1
...

output:

1000

result:

ok answer is '1000'

Test #9:

score: 0
Accepted
time: 46ms
memory: 16444kb

input:

300 44850 150
1 2 4
1 3 4
1 4 4
1 5 3
1 6 10
1 7 4
1 8 8
1 9 5
1 10 4
1 11 9
1 12 9
1 13 1
1 14 3
1 15 5
1 16 7
1 17 5
1 18 2
1 19 6
1 20 4
1 21 10
1 22 5
1 23 7
1 24 2
1 25 2
1 26 4
1 27 4
1 28 5
1 29 8
1 30 10
1 31 9
1 32 1
1 33 7
1 34 5
1 35 4
1 36 6
1 37 8
1 38 1
1 39 2
1 40 1
1 41 1
1 42 1
1 43...

output:

249

result:

ok answer is '249'

Test #10:

score: 0
Accepted
time: 59ms
memory: 16388kb

input:

300 44850 150
1 2 70
1 3 26
1 4 76
1 5 74
1 6 98
1 7 72
1 8 66
1 9 25
1 10 36
1 11 57
1 12 8
1 13 88
1 14 98
1 15 33
1 16 85
1 17 56
1 18 16
1 19 62
1 20 41
1 21 81
1 22 18
1 23 15
1 24 69
1 25 11
1 26 29
1 27 62
1 28 64
1 29 41
1 30 92
1 31 29
1 32 99
1 33 40
1 34 30
1 35 23
1 36 49
1 37 6
1 38 84
...

output:

1299

result:

ok answer is '1299'

Test #11:

score: 0
Accepted
time: 65ms
memory: 16032kb

input:

300 44850 150
1 2 3
1 3 2
1 4 20
1 5 77
1 6 77
1 7 23
1 8 39
1 9 57
1 10 83
1 11 60
1 12 6
1 13 78
1 14 64
1 15 62
1 16 41
1 17 88
1 18 77
1 19 58
1 20 39
1 21 18
1 22 43
1 23 26
1 24 40
1 25 61
1 26 23
1 27 6
1 28 47
1 29 100
1 30 59
1 31 92
1 32 60
1 33 13
1 34 57
1 35 55
1 36 99
1 37 77
1 38 63
1...

output:

1310

result:

ok answer is '1310'

Test #12:

score: -100
Wrong Answer
time: 16ms
memory: 16408kb

input:

300 44551 299
1 2 1
1 3 1
1 4 1
1 5 1
1 6 1
1 7 1
1 8 1
1 9 1
1 10 1
1 11 1
1 12 1
1 13 1
1 14 1
1 15 1
1 16 1
1 17 1
1 18 1
1 19 1
1 20 1
1 21 1
1 22 1
1 23 1
1 24 1
1 25 1
1 26 1
1 27 1
1 28 1
1 29 1
1 30 1
1 31 1
1 32 1
1 33 1
1 34 1
1 35 1
1 36 1
1 37 1
1 38 1
1 39 1
1 40 1
1 41 1
1 42 1
1 43 1
...

output:

333333

result:

wrong answer expected '-1', found '333333'