Submission #36576258

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<(int)n;i++)
#define per(i,a,n) for (int i=n;i-->(int)a;)
int read(){int r;scanf("%d",&r);return r;}

class TwoSat{
  vector<int> low; // 能达到的最小的点
  vector<int> dfn; // tarjan 用的深搜访问次序标识
  stack<int> stk; // tarjan 用的stk
  vector<int> res; // tarjan 结果
  vector<vector<int> > p; // 所有点
  int n;
  void scc(int v) {
    static int id = 0;
    low[v] = dfn[v] = id++;
    stk.push(v);
    for(auto w:p[v]){
      if(dfn[w] == -1){ // 未访问过
        scc(w);
        low[v] = min(low[v],low[w]);
      } else if(res[w] == -1){ // 访问过但没有结果(在栈中)
        low[v] = min(low[v],dfn[w]);
      }
    }
    int u;
    if(low[v] == dfn[v])  {
      do{
        res[u = stk.top()] = v;
        stk.pop();
      }while(u != v);
    }
  }
public:
  TwoSat(int SZ):n(SZ){ // 点范围[0..SZ-1]
    low = vector<int>(2*n,-1);
    dfn = vector<int>(2*n,-1);
    stk = {};
    res = vector<int> (2*n,-1);
    p = vector<vector<int> >(2*n);
  }

  bool calc(vector<bool> & ans){
    rep(i,0,2*n) if(res[i]==-1)scc(i);
    rep(i,0,n) if(res[i*2]==res[i*2+1])return false; // 同一个块的真假都在一个scc里
    vector<int> revscc(2*n); // 互斥scc
    rep(i,0,n) { // 每个点的true/false 状态互斥
      revscc[res[i*2]] = res[i*2+1];
      revscc[res[i*2+1]] = res[i*2];
    }
    vector<set<int> > scc2scc(2*n);
    unordered_map<int,int> degree; // scc入度
    rep(i,0,2*n) { // 跨scc的反向边, 做拓扑选择, (因为scc计算后,剩下的一定是偏序不会有环)
      degree[res[i]] = 0;
      for(auto j:p[i]) if(res[i]!=res[j]) scc2scc[res[j]].insert(res[i]); // i -> j 反向边
    }
    for(auto &s:scc2scc) for(auto t:s) degree[t]++;
    vector<int> d0; // 入度为0
    for(auto [v,d]: degree) if(!d) d0.push_back(v);
    unordered_map<int,bool> sccpick; // scc 选/不选
    rep(i,0,d0.size()) {
      if(!sccpick.count(d0[i])){ // 没有计算过
        // prinpick("pick %d, unpick %d\n",d0[i],revscc[d0[i]]);
        sccpick[d0[i]] = true;
        sccpick[revscc[d0[i]]] = false;
      }
      for(auto item:scc2scc[d0[i]]) if(!(--degree[item])) d0.push_back(item); // 更新入度排序
    }
    ans = vector<bool>(n);
    rep(i,0,n) ans[i] = sccpick[res[i*2+1]];
    return true;
  }
  void then(pair<int,bool> pi, pair<int,bool> pj){ // {i,true/false} -> {j,true/false}
    auto [i,bi] = pi;
    auto [j,bj] = pj;
    assert(i >= 0 && i < n);
    assert(j >= 0 && j < n);
    p[2*i+bi].push_back(2*j+bj);
    if(2*i+bi!=2*j+(!bj)) p[2*j+(!bj)].push_back(2*i+(!bi)); // 自动建立逻辑边
  }
};

// ---------------- lib ----------------

int main(){
  int n = read();
  int m = read(); // xi \in [0,m]
  int q = read();
  TwoSat ts(n*(m+1));
  auto _=[&](int i,int v){return i*(m+1)+v;}; // 编码 a[i] (>=v false, < v true)
  auto ge=[&](int i,int v){return pair<int,bool>{_(i,v),false};}; // greater equal than
  auto lt=[&](int i,int v){return pair<int,bool>{_(i,v),true};}; // less than
  auto chk=[&](int v){return 0<=v && v<=m;};
  rep(i,0,n) rep(v,1,m+1) ts.then(ge(i,v),ge(i,v-1)); // a[i]>=x 则 a[i] >= x-1 小于自动对称逻辑边
  // 不能 < 0, 所以建立 < 0 则 >= 0
  rep(i,0,n) ts.then(lt(i,0),ge(i,0));
  while(q--){
    int i=read()-1;
    int j=read()-1;
    int mn = read();
    int mx = read();
    // a[i]+a[j] >= x = mn, a[i] < v 则 a[j] >= x-v+1
    rep(v,0,m+1) if(chk(mn-v+1)) ts.then(lt(i,v),ge(j,mn-v+1)); // j到i 自动对称
    if(chk(mn-m)){ // mn-v+1 < 0的话 就是全部都可以 不需要建立失败逻辑, 而 a[j] >= x-v+1 > m 才需要
      int v=mn-m;
      ts.then(lt(i,v),ge(i,v));
      ts.then(lt(j,v),ge(j,v));
    }
    // a[i]+a[j] <= x = mx, a[i] >= v 则 aj < x-v+1
    rep(v,1,m+1) if(chk(mx-v+1)) ts.then(ge(i,v),lt(j,mx-v+1)); // j到i 自动对称
    if(chk(mx+1)){ // 同理 建立失败逻辑
      int v=mx+1;
      ts.then(ge(i,v),lt(i,v));
      ts.then(ge(j,v),lt(j,v));
    }
  }

  vector<bool> res= {};
  bool ok = ts.calc(res); // scc 联通分量 标识
  if(!ok){
    printf("-1\n");
    return 0;
  }
  rep(i,0,n) per(v,0,m+1) if(!res[_(i,v)]){ // a[i] >= v
    printf("%d ",v);// ans[i] = v;
    break;
  }
  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int read()’:
./Main.cpp:5:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
    5 | int read(){int r;scanf("%d",&r);return r;}
      |                  ~~~~~^~~~~~~~~

Judge Result