QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #283086 | #1359. Setting Maps | ChrysanthBlossom | WA | 3ms | 5704kb | C++14 | 2.8kb | 2023-12-13 20:04:55 | 2023-12-13 20:04:55 |
Judging History
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