[二分 前缀优化建图 2-SAT] Codeforces 587D. Duff in Mafia

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
const int N=1000010;
int n,m,cnt,tot,G[N];
struct iedge{
int s,t,w,c,g;
}ie[N];
int tmp[N],icnt;
vector<iedge> e[N];
struct edge{
int t,nx;
}E[N<<1];
inline void addedge(int x,int y,int c,int t,int g){
e[x].push_back({x,y,t,c,g}); e[y].push_back({x,y,t,c,g});
}
vector<int> cc[N];
int tt[N],iit;
inline void addedge(int x,int y){
//cout<<x<<' '<<y<<endl;
E[++cnt].t=y; E[cnt].nx=G[x]; G[x]=cnt;
}
int vis[N],g[N],dfn[N],low[N],s[N],tp,iiit,ig;
void tarjan(int x){
dfn[x]=low[x]=++iiit; vis[x]=1; s[++tp]=x;
for(int i=G[x];i;i=E[i].nx){
if(!vis[E[i].t]) tarjan(E[i].t);
if(vis[E[i].t]!=2) low[x]=min(low[x],low[E[i].t]);
}
if(dfn[x]==low[x]){
int k; ++ig;
do{ k=s[tp--]; vis[k]=2; g[k]=ig; }while(tp && k!=x);
}
}
int lst[N];
inline bool check(int x){
memset(G,0,sizeof(G)); cnt=0;
memset(vis,0,sizeof(vis));
for(int i=1;i<=m;i++)
if(ie[i].w>x) addedge(i<<1|1,i<<1);
tot=(m<<1|1)+1;
for(int i=1;i<=n;i++){
++iit;
vector<int> a,b;
for(auto u : e[i]){
if(tt[u.c]!=iit) tt[u.c]=iit,cc[u.c].clear(),a.push_back(u.c);
cc[u.c].push_back(u.g); b.push_back(u.g);
}
if(!b.size()) continue;
addedge(b[0]<<1|1,tot); addedge(tot+1,b[0]<<1);
for(int j=1;j<b.size();j++){
addedge(tot+(j-1<<1),tot+(j<<1));
addedge(tot+(j<<1|1),tot+(j-1<<1|1));
addedge(b[j]<<1|1,tot+(j<<1));
addedge(tot+(j<<1|1),b[j]<<1);
addedge(b[j]<<1|1,tot+(j-1<<1|1));
addedge(tot+(j-1<<1),b[j]<<1);
}
tot+=(b.size()<<1|1)+1;
for(int u : a){
if(cc[u].size()<2) continue;
addedge(cc[u][0]<<1,tot);
addedge(tot+1,cc[u][0]<<1|1);
for(int j=1;j<cc[u].size();j++){
addedge(tot+(j-1<<1),tot+(j<<1));
addedge(tot+(j<<1|1),tot+(j-1<<1|1));
addedge(cc[u][j]<<1,tot+(j<<1));
addedge(tot+(j<<1|1),cc[u][j]<<1|1);
addedge(cc[u][j]<<1,tot+(j-1<<1|1));
addedge(tot+(j-1<<1),cc[u][j]<<1|1);
}
tot+=(cc[u].size()<<1|1)+1;
}
}
tp=iiit=ig=0;
for(int i=2;i<=tot;i++)
if(!vis[i]) tarjan(i);
for(int i=1;i<=m;i++)
if(g[i<<1]==g[i<<1|1]) return false;
memcpy(lst,g,sizeof(g));
return true;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1,x,y,c,t;i<=m;i++)
scanf("%d%d%d%d",&x,&y,&c,&t),ie[i]={x,y,t,c,i},tmp[++icnt]=c;
sort(tmp+1,tmp+1+icnt); icnt=unique(tmp+1,tmp+1+icnt)-tmp-1;
for(int i=1;i<=m;i++) ie[i].c=lower_bound(tmp+1,tmp+1+icnt,ie[i].c)-tmp;
for(int i=1;i<=m;i++) addedge(ie[i].s,ie[i].t,ie[i].c,ie[i].t,i);
int l=0,r=1e9,mid,ans=-1;
//int ss=check(3);
while(l<=r)
check(mid=l+r>>1)?r=(ans=mid)-1:l=mid+1;
vector<int> pt;
if(!~ans) return puts("No"),0;
puts("Yes");
for(int i=1;i<=m;i++)
if(lst[i<<1|1]<lst[i<<1]) pt.push_back(i);
printf("%d %dn",ans,pt.size());
for(int u : pt) printf("%d ",u);
return 0;
}