QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#283086#1359. Setting MapsChrysanthBlossomWA 3ms5704kbC++142.8kb2023-12-13 20:04:552023-12-13 20:04:55

Judging History

This is the latest submission verdict.

  • [2023-12-13 20:04:55]
  • Judged
  • Verdict: WA
  • Time: 3ms
  • Memory: 5704kb
  • [2023-12-13 20:04:55]
  • Submitted

answer

#include<bits/stdc++.h>
#define ri register int
#define ll long long 
using namespace std;
const int maxn=1e4+7;
int cnt=1,head[maxn],to[maxn],nxt[maxn],bq[maxn];
int id[maxn];
void add(int u,int v,int w,int i){
	++cnt;
//	cout<<u<<' '<<v<<' '<<w<<' '<<i<<endl;
	to[cnt]=v;bq[cnt]=w;id[cnt]=i;
	nxt[cnt]=head[u];
	head[u]=cnt;
}
int in[maxn][30],out[maxn][30];
int n,m,k;
int tot;
const ll inf=1e9;
int cost[maxn];
int ss,tt;
int dis[maxn];
queue<int>q;
bool bfs(){
	for(ri i=1;i<=tot;i++)dis[i]=inf;
	dis[ss]=0;
	while(!q.empty())q.pop();
	q.push(ss);
	while(!q.empty()){
		int u=q.front();q.pop();
//		cout<<u<<endl;
		for(ri e=head[u];e;e=nxt[e]){
			int v=to[e],w=bq[e];
			if(w&&dis[v]>dis[u]+1){
				dis[v]=dis[u]+1;
				q.push(v);
				if(v==tt)return 1;
			}
		}
	}
	return 0;
}
int now[maxn];
ll dfs(int u,ll s){
	if(u==tt||s==0)return s;
//	cout<<u<<endl;
	ll res=0;
	for(ri e=now[u];e;e=nxt[e]){
		now[u]=e;
		int v=to[e],w=bq[e];
		if(w&&dis[v]==dis[u]+1){
			ll k=dfs(v,min(s,1ll*w));
			bq[e]-=k;
			bq[e^1]+=k;
			res+=k;
			s-=k;
		}
	}
	if(!res)dis[u]=inf;
	return res;
}
bool vis[maxn][2];
void bfs2(int st,int id){
	for(ri i=1;i<=tot;i++)vis[i][id]=0;
	vis[st][id]=1;
	while(!q.empty())q.pop();
	q.push(st);
	while(!q.empty()){
		int u=q.front();q.pop();
		for(ri e=head[u];e;e=nxt[e]){
			int v=to[e],w=bq[e];
			if(!w)continue;
			if(!vis[v][id])q.push(v);
			vis[v][id]=1;
		} 
	}
}
signed main(){
//	ios::sync_with_stdio(0);
	cin>>n>>m>>k;
	cin>>ss>>tt;
	for(ri i=1;i<=n;i++)cin>>cost[i];
	for(ri i=1;i<=n;i++){
		for(ri j=0;j<=k;j++){
			in[i][j]=++tot;
			out[i][j]=++tot;
		}
	}
	for(ri i=1;i<=n;i++){
		for(ri j=0;j<k;j++){
			for(ri x=j+1;x<k;x++){
				add(in[i][j],out[i][x],inf,inf);
				add(out[i][x],in[i][j],0,inf);
			}
		}
	}
	for(ri i=1;i<=n;i++){
		for(ri j=0;j<k;j++){
			add(in[i][j],out[i][j],cost[i],i);
			add(out[i][j],in[i][j],0,inf);
		}
	}
	for(ri i=1;i<=m;i++){
		int u,v;cin>>u>>v;
		for(ri j=0;j<k;j++){
			add(out[u][j],in[v][j],inf,inf);
			add(in[v][j],out[u][j],0,inf);
		}
	}
	ss=in[ss][0],tt=out[tt][k-1];
	ll ans=0;
	while(bfs()){
//		cout<<endl;
		for(ri i=1;i<=tot;i++)now[i]=head[i];
		ans+=dfs(ss,inf*inf);
	}
	if(ans>2e9)cout<<-1<<endl;
	else{
		bfs2(ss,0);
		int c=0;
		for(ri i=1;i<=n;i++){
			for(ri j=0;j<k;j++){
//				cout<<i<<' '<<j<<' '<<vis[in[i][j]][0]<<' '<<(!vis[out[i][j]][0])<<endl;
				if(vis[in[i][j]][0]&&!vis[out[i][j]][0])c++;
			}
		}
//		cout<<ans<<endl;
//		for(ri i=1;i<=cnt;i++){
//			cout<<bq[i]<<' '<<to[i]<<' '<<id[i]<<endl;
//		}
		cout<<c<<endl;
		for(ri i=1;i<=n;i++){
			for(ri j=0;j<k;j++){
				if(vis[in[i][j]][0]&&!vis[out[i][j]][0])cout<<i<<endl;
			}
		}
	}
	return 0;
}
/*
7 11 1
1 7
100 5 7 16 11 12 100
1 2
1 3
1 4
1 5
2 3
2 6
3 6
4 3
4 7
5 7
6 7
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3904kb

input:

3 2 5
1 3
1 60 35
1 2
2 3

output:

-1

result:

ok answer = IMPOSSIBLE

Test #2:

score: 0
Accepted
time: 1ms
memory: 5628kb

input:

7 11 1
1 7
100 5 7 16 11 12 100
1 2
1 3
1 4
1 5
2 3
2 6
3 6
4 3
4 7
5 7
6 7

output:

4
2
3
4
5

result:

ok answer = 39

Test #3:

score: 0
Accepted
time: 0ms
memory: 3672kb

input:

11 17 2
1 11
1000 10 10 10 10 10 10 10 10 10 1000
1 2
1 3
1 4
1 5
1 6
2 7
3 7
4 7
5 8
6 8
7 8
7 9
7 10
8 9
8 11
9 11
10 11

output:

6
5
6
7
8
9
10

result:

ok answer = 60

Test #4:

score: 0
Accepted
time: 0ms
memory: 3864kb

input:

2 2 2
2 1
100 200
1 2
2 1

output:

2
1
2

result:

ok answer = 300

Test #5:

score: 0
Accepted
time: 0ms
memory: 3644kb

input:

5 5 5
1 5
1 1 1 1 1
1 2
2 3
3 4
4 5
1 5

output:

-1

result:

ok answer = IMPOSSIBLE

Test #6:

score: 0
Accepted
time: 0ms
memory: 3740kb

input:

100 120 5
1 5
5367720 2854323 1799056 9744604 3215334 7580413 6269402 3208439 8812449 3297484 2047196 4044341 7514502 2928715 9335004 3935096 6660663 3356480 4801491 5786147 895995 6710240 222342 4469390 1543213 6678041 8838445 6741919 8138951 5273670 8983795 5131484 4245746 7460466 8357966 8464419 ...

output:

-1

result:

ok answer = IMPOSSIBLE

Test #7:

score: 0
Accepted
time: 0ms
memory: 3868kb

input:

2 1 5
1 2
10 10
1 2

output:

-1

result:

ok answer = IMPOSSIBLE

Test #8:

score: 0
Accepted
time: 0ms
memory: 3980kb

input:

154 304 2
67 7
10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 100000...

output:

2
7
67

result:

ok answer = 20000000

Test #9:

score: 0
Accepted
time: 0ms
memory: 3612kb

input:

75 146 1
15 2
10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 1000000...

output:

1
15

result:

ok answer = 10000000

Test #10:

score: 0
Accepted
time: 0ms
memory: 3808kb

input:

182 360 4
97 110
10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 1000...

output:

-1

result:

ok answer = IMPOSSIBLE

Test #11:

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

input:

136 268 5
132 5
10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000...

output:

-1

result:

ok answer = IMPOSSIBLE

Test #12:

score: -100
Wrong Answer
time: 1ms
memory: 3796kb

input:

200 396 3
174 124
10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 100...

output:

2
124
174

result:

wrong answer Given vertex set from user output does not cover k vertices in some path