Submission #2246569


Source Code Expand

#include <bits/stdc++.h>
using namespace std;

template<class Data> struct Graph;

struct DefData {
  struct VData {};
  struct GData {};

  using Len = int;
  struct EData {
    Len len;
    EData() : len(1) {}
  };
  static const Len INF = 0x33433433;
};

template<class Data=DefData>
struct Graph {
  using VData = typename Data::VData;
  using EData = typename Data::EData;
  using GData = typename Data::GData;
  struct Edge {
    int to;
    int rev_idx;
    bool is_es;
    EData dat;
  };
  using Len = typename remove_const<decltype(Data::INF)>::type;
  using Ls = vector<Len>;
  using Es = vector<Edge>;
  Len INF = Data::INF;

  int n;
  GData gdat;
  vector<VData> vdat;
  vector<Es> es;
  vector<Es> res;
  vector<Ls> cost;
  
  Graph() {}
  Graph(int sz) {
    Init(sz);
  }

  void Init(int sz) {
    n = sz;
    vdat.resize(sz);
    es.resize(sz);
    res.resize(sz);
  }

  void AddEdge(int u, int v, EData d, EData r) {
    es[u].emplace_back(Edge{v, 0, true, d});
    res[v].emplace_back(Edge{u, 0, false, r});
    es[u].back().rev_idx = res[v].size()-1;
    res[v].back().rev_idx = es[u].size()-1;
  }

  void AddEdge(int u, int v, EData d=EData()) {
    AddEdge(u, v, d, d);
  }

  void AddEdgeForFlow(int u, int v, EData d) {
    AddEdge(u, v, d, EData());
  }

  Edge *GetRevEdge(Edge *e) {
    int v = e->to;
    if (e->is_es) return &res[v][e->rev_idx];
    return &es[v][e->rev_idx];
  }

  // should be tested
  template<class Cmp>
  void EraseMultipleEdge(Cmp cmp, bool really_erase) {
    auto same = [](const Edge &a, const Edge &b) {
      return a.to == b.to;
    };

    vector<Es> new_res(n);
    for (int v=0; v<n; v++) {
      auto &ves = es[v];
      sort(ves.begin(), ves.end(), cmp);
      auto itr = unique(ves.begin(), ves.end(), same);
      if (really_erase) ves.erase(itr, ves.end());
      for (int i=0; i<ves.size(); i++) {
        auto &e = ves[i];
        int u = e.to;
        new_res[u].emplace_back(Edge{v, i, false, GetRevEdge(&e)->dat});
      }
    }
    res.swap(new_res);
  }

  void CreateAdjMat() {
    cost.clear();
    cost.resize(n, Ls(n, INF));

    auto cmp = [](const Edge &a, const Edge &b) {
      if (a.to != b.to) return a.to < b.to;
      return a.dat.len < b.dat.len;
    };
    EraseMultipleEdge(cmp, false);

    for (int i=0; i<n; i++) {
      int prev = -1;
      for (auto &e : es[i]) {
        int v = e.to;
        if (prev > v) break;
        cost[i][v] = min(cost[i][v], e.dat.len);
        prev = v;
      }
    }
  }

  void DijkstraV(vector<int> &starts, Ls &d) {
    d.clear();
    d.resize(n, INF);
    for (int s : starts) d[s] = 0;

    if (cost.empty()) CreateAdjMat();

    vector<bool> used(n, false);
    for (int i=0; i<n; i++) {
      int v = -1;
      for (int u=0; u<n; u++) {
        if (used[u]) continue;
        if (v == -1 || d[u] < d[v]) {
          v = u;
        }
      }
      if (v == -1) return;

      used[v] = true;
      for (int u=0; u<n; u++) {
        d[u] = mind(d[u], d[v] + cost[v][u]);
      }
    }

    // must not reach here
    assert(0);
  }

  void DijkstraE(vector<int> &starts, Ls &d) {
    using Pair = pair<Len, int>;
    priority_queue<Pair, vector<Pair>, greater<Pair> > q;
    d.clear();
    d.resize(n, INF);
    for (int s : starts) {
      d[s] = 0;
      q.push(Pair(0, s));
    }

    while (!q.empty()) {
      Pair p = q.top(); q.pop();
      int v = p.second;
      if (d[v] < p.first) continue;
      for (auto &e : es[v]) {
        int u = e.to;
        Len nd = d[v] + e.dat.len;
        if (d[u] > nd) {
          d[u] = nd;
          q.push(Pair(nd, u));
        }
      }
    }
  }

  // return true if a graph has a negative cycle in the reachnable scope from starts
  bool SPFA(vector<int> &starts, Ls &d) {
    d.clear();
    d.resize(n, INF);

    if (n == 1) {
      d[0] = 0;
      return false;
    }

    queue<int> q;
    vector<bool> inq(n);
    vector<int> cnt(n);
    for (int s : starts) {
      inq[s] = true;
      q.push(s);
      d[s] = 0;
    }

    while (!q.empty()) {
      int v = q.front(); q.pop();
      inq[v] = false;
      cnt[v]++;
      if (cnt[v] > n) continue;
      for (auto &e : es[v]) {
        int u = e.to;
        Len nd = d[v] + e.dat.len;
        if (d[u] > nd) {
          d[u] = nd;
          if (inq[u]) continue;
          inq[u] = true;
          q.push(u);
        }
      }
    }

    // do DFS if you need the concrete contents of such cycles
    for (int i=0; i<n; i++) {
      if (cnt[i] >= n) return true;
    }

    return false;
  }

  void DijkstraV(int s, Ls &d) {
    vector<int> ss(1, s);
    DijkstraV(ss, d);
  }

  void DijkstraE(int s, Ls &d) {
    vector<int> ss(1, s);
    DijkstraE(ss, d);
  }

  // return true if the graph has a negative cycle
  bool SPFA(int s, Ls &d) {
    vector<int> ss(1, s);
    return SPFA(ss, d);
  }

  // Create "Shortest Path Graph", which should be DAG
  Graph<Data> RestoreShortestPaths(Ls &d) {
    Graph<Data> ret(n);

    for (int i=0; i<n; i++) {
      for (auto &e : es[i]) {
        int v = e.to;
        if (d[v] == d[i] + e.dat.len) {
          ret.AddEdge(i, e.to, e.dat, GetRevEdge(&e)->dat);
        }
      }
    }

    return ret;
  }

  bool hasNegativeCycle() {
    vector<int> s(n);
    Ls d;
    for (int i=0; i<n; i++) s[i] = i;
    return SPFA(s, d);
  }

  // return true if the graph has a negative cycle
  bool FloydWarshall(vector<Ls> &ds) {
    if (cost.empty()) CreateAdjMat();

    ds = vector<Ls>(cost);
    for (int i=0; i<n; i++) {
      ds[i][i] = min(ds[i][i], Len(0));
    }

    for (int k=0; k<n; k++) {
      for (int i=0; i<n; i++) {
        if (ds[i][k] == INF) continue;
        for (int j=0; j<n; j++) {
          if (ds[k][j] == INF) continue;
          Len nd = max(ds[i][k] + ds[k][j], -INF);
          if (ds[i][j] > nd) {
            ds[i][j] = nd;
          }
        }
      }
    }

    for (int i=0; i<n; i++) {
      if (ds[i][i] < 0) return true;
    }
    return false;
  }

  // Karp's Algorithm O(NM)
  // should be tested
  // should be used for SCC
  double MinimumMeanCycle() {
    vector<Ls> dp(n+1, Ls(n, INF));

    dp[0][0] = 0;
    for (int i=1; i<=n; i++) {
      for (int v=0; v<n; v++) {
        for (auto &e : es[v]) {
          int u = e.to;
          dp[i][u] = min(dp[i][u], dp[i-1][v] + e.dat.len);
        }
      }
    }

    double ret = 1.0/0.0;
    for (int v=0; v<n; v++) {
      double alpha = (-1.0)/0.0;
      for (int i=1; i<n; i++) {
        if (dp[n][v] == INF) continue;
        if (dp[i][v] == INF) continue;
        alpha = max(alpha, (dp[n][v]-dp[i][v])/double(n-i));
      }
      ret = min(ret, alpha);
    }
    return ret;
  }

  Len Dinic(int s, int t) {
    vector<int> level, iter;
    vector<bool> sweep_res; 

    function<Len(int,int,Len)> dfs;
    dfs = [&](int s, int u, Len crr) {
      if (s == u || crr == 0) return crr;
      Len sum = 0;

      while (1) {
        auto &ues = sweep_res[u] ? res[u] : es[u];
        for (int &i=iter[u]; i<ues.size(); i++) {
          Edge *e = &ues[i];
          Edge *re = GetRevEdge(e);
          int v = e->to;
          if (level[v] >= level[u] || re->dat.cap <= 0) continue;
          Len f = dfs(s, v, min(crr-sum, re->dat.cap));
          if (f <= 0) continue;
          re->dat.cap -= f;
          e->dat.cap += f;
          sum += f;
          if (sum >= crr) break;
        }

        if (sweep_res[u] && iter[u] == ues.size()) break;
        if (iter[u] == ues.size() && !sweep_res[u]) {
          sweep_res[u] = true;
          iter[u] = 0;
        }
      }

      return sum;
    };

    vector<int> q(n);
    Len flow = 0;
    while (1) {
      level.assign(n, -1);
      int ql = 0;
      int qr = 0;
      level[ q[qr++] = s ] = 0;
      while (ql != qr && level[t] == -1) {
        int u = q[ql++];
        for (auto &e : es[u]) {
          if (e.dat.cap > 0 && level[e.to] == -1) {
            level[ q[qr++] = e.to ] = level[u] + 1;
          }
        }

        for (auto &e : res[u]) {
          if (e.dat.cap > 0 && level[e.to] == -1) {
            level[ q[qr++] = e.to ] = level[u] + 1;
          }
        }
      }
      if (level[t] == -1) return flow;
      iter.assign(n, 0);
      sweep_res.assign(n, false);
      flow += dfs(s, t, INF);
    }
  }

  //Len Fujishige
};

template<class Data=DefData>
struct DFSForest {
  using G = Graph<Data>;
  using Edge = typename G::Edge;
  using Brid = pair<int, Edge*>;

  int grp;
  vector<int> ord;
  vector<int> low;
  vector<int> belong;
  vector<int> artic;
  vector<Brid> bridge;

  DFSForest() {}
  DFSForest(G &g, bool is_directed) {
    Init(g, is_directed);
  }
  
  void Init(G &g, bool is_directed) {
    int k = 0;
    int idx = 0;
    int n = g.n;
    vector<int> st(n);

    grp = 0;
    ord.resize(n, -1);
    low.resize(n);
    belong.resize(n, -1);

    function<void(int,int,Edge*)> dfs;
    // to deal with multiple edges, it uses a pointer
    auto update = [&](int v, Edge *e, bool &is_artic, int &cnt) {
      int u = e->to;
      if (ord[u] != -1) {
        if (belong[u] == -1) low[v] = min(low[v], ord[u]);
      } else {
        cnt++;
        dfs(u, v, e);
        low[v] = min(low[v], low[u]);
        if (ord[v] <= low[u]) is_artic = true;
        if (ord[v] < low[u]) bridge.emplace_back(Brid(v, e));
      }
    };

    dfs = [&](int v, int p, Edge *par) {
      bool is_artic = false;
      int cnt = 0;

      st[idx++] = v;
      low[v] = ord[v] = k++;

      for (auto &e : g.es[v]) {
        if (g.GetRevEdge(&e) == par) continue;
        update(v, &e, is_artic, cnt);
      }

      if (!is_directed) {
        for (auto &e : g.res[v]) {
          if (g.GetRevEdge(&e) == par) continue;
          update(v, &e, is_artic, cnt);
        }
      }

      if (p == -1) is_artic = (cnt > 1);
      if (is_artic) artic.emplace_back(v);

      if (low[v] != ord[v]) return;
      while (1) {
        int u = st[--idx];
        belong[u] = grp;
        if (u == v) break;
      }
      grp++;
    };

    for (int i=0; i<n; i++) {
      if (ord[i] == -1) dfs(i, -1, NULL);
    }
  }
};


template<class Data=DefData>
struct SCCData {
  using VD = typename Data::VData;
  using ED = typename Data::EData;
  using GD = typename Data::GData;
  using G = Graph<Data>;
  using Len = int;

  struct VData {
    G g; // the graph consisting of contracted nodes in one component
    vector<int> cont2orig; // the correspondence of the node index: v on SCCVData::g -> cont2orig[v] on the original graph(G)
  };

  struct EData : ED {
    int s;
    int t;
    EData(int a, int b, const ED &dat) : ED(dat), s(a), t(b) {}
  };

  struct GData {
    vector<int> orig2cont; // the correspondence of the node index: v on G -> orig2cont[v] on G's SCC::vdat[belong[v]].g
  };

  static const Len INF = 0x33433433;
};

template<class Data=DefData>
struct SCC : Graph<SCCData<Data> > {
  using ED = typename Data::EData;
  using EData = typename SCCData<Data>::EData;
  using G = Graph<Data>;

  DFSForest<Data> df;
  SCC(G &g) : df(g, true) {
    int n = g.n;

    this->Init(df.grp);
    auto &gdat = this->gdat;
    auto &vdat = this->vdat;

    gdat.orig2cont.resize(n);
    for (int v=0; v<n; v++) {
      auto &vd = vdat[df.belong[v]];
      gdat.orig2cont[v] = vd.cont2orig.size();
      vd.cont2orig.emplace_back(v);
    }

    for (int i=0; i<df.grp; i++) {
      auto &vd = vdat[i];
      vd.g.Init(vd.cont2orig.size());
    }
    
    for (int v=0; v<n; v++) {
      for (auto &e : g.es[v]) {
        int u = e.to;
        ED &rd = g.GetRevEdge(&e)->dat;
        int bv = df.belong[v];
        int bu = df.belong[u];

        if (bv == bu) {
          auto &vd = vdat[bv];
          auto &dic = gdat.orig2cont;
          vd.g.AddEdge(dic[v], dic[u], e.dat, rd);
        } else {
          this->AddEdge(bv, bu, EData(v, u, e.dat), EData(u, v, rd));
        }
      }
    }
  }
};

using LLI = long long int;

typedef DefData A;
typedef Graph<A> G;
typedef DFSForest<A> D;

int N;
int M;
G g;
D d;
bool used[114514];
int ord[114514];
deque<int> ans, ans2;

deque<int> dfs(int v, int ig=0) {
  deque<int> ret;

  for (auto &e : g.es[v]) {
    int u = e.to;
    if (d.ord[u] < d.ord[v]) continue;
    if (ig == 0) ret = dfs(u);
    ig--;
  }
  ret.emplace_back(v);
  return ret;
}

int dfs2(int v) {
  int num_child = 0;
  bool to_root = false;
  for (auto &e : g.es[v]) {
    int u = e.to;
    if (u == 0) to_root = true;
    if (ord[u] < ord[v]) continue;
    num_child++;
  }

  int exc_u;
  int type = 0;
  for (auto &e : g.es[v]) {
    int u = e.to;
    if (ord[u] < ord[v]) continue;

    //printf("%d -> %d\n", v, u);
    type = dfs2(u);
    if (type == 1) {
      exc_u = u;
      break;
    } else if (type == 2) break;
  }

  //if (type == 1) printf("v: %d exc_u: %d num_child: %d\n", v, exc_u, num_child);

  if (type == 1 && num_child >= 2) {
    //printf("branch: %d\n", v);
    for (auto &e : g.es[v]) {
      int u = e.to;
      if (ord[u] < ord[v]) continue;
      if (u == exc_u) continue;
      //printf("toward: %d\n", u);
      ans2 = dfs(u);
      reverse(ans2.begin(), ans2.end());
      break;
    }
    type = 2;
  }

  if (type == 0 && num_child == 0 && to_root) {
    type = 1;
    //printf("found: %d\n", v);
  }

  if (type == 1) {
    ans.emplace_front(v);
  } else if (type == 2) {
    ans2.emplace_front(v);
  }

  return type;
}

deque<int> dfs3(int v, int ig=0) {
  deque<int> ret;
  used[v] = true;

  for (auto &e : g.es[v]) {
    int u = e.to;
    if (used[u]) continue;
    if (ig == 0) {
      ret = dfs3(u);
      break;
    } else dfs3(u, -1);
    ig--;
  }
  ret.emplace_back(v);
  return ret;
}

void dfs4(int v, int p) {
  ord[v] = ord[p]+1;
  for (auto &e : g.es[v]) {
    int u = e.to;
    if (ord[u] != -1) continue;
    dfs4(u, v);
  }
}

int main() {
  scanf("%d%d", &N, &M);
  g.Init(N);
  for (int i=0; i<M; i++) {
    int a, b;
    scanf("%d%d", &a, &b);
    --a;
    --b;
    g.AddEdge(a, b);
    g.AddEdge(b, a);
  }

  d.Init(g, true);

  /*printf("artic: ");
  for (auto v : d.artic) {
    printf("%d ", v);
  }puts("");*/

  if (!d.artic.empty()) {
    ans = dfs3(d.artic[0]);
    //for (auto v : ans) printf("%d ", v);
    //puts("");
    fill(used, used+N, false);
    ans2 = dfs3(d.artic[0], 1);
    //for (auto v : ans2) printf("%d ", v);
    //puts("");
    ans2.pop_back();
    reverse(ans2.begin(), ans2.end());
    ans.insert(ans.end(), ans2.begin(), ans2.end());
  } else if (g.es[0].size() <= 1) {
    ans = dfs(0);
  } else {
    for (int i=0; i<N; i++) {
      fill(ord, ord+N, -1);
      dfs4(i, i);
      dfs2(i);
      ans.insert(ans.end(), ans2.begin(), ans2.end());
      if (!ans.empty()) break;
    }
  }

  printf("%d\n", (int)ans.size());
  for (int v : ans) {
    printf("%d ", v+1);
  }
  puts("");
}

Submission Info

Submission Time
Task B - Hamiltonish Path
User potetisensei
Language C++14 (GCC 5.4.1)
Score 0
Code Size 15432 Byte
Status WA
Exec Time 219 ms
Memory 100720 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:636:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &N, &M);
                        ^
./Main.cpp:640:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &a, &b);
                          ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 500
Status
AC × 3
AC × 17
WA × 2
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All sample_01.txt, sample_02.txt, sample_03.txt, sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt
Case Name Status Exec Time Memory
sample_01.txt AC 1 ms 256 KB
sample_02.txt AC 1 ms 256 KB
sample_03.txt AC 1 ms 256 KB
subtask_1_01.txt AC 70 ms 18432 KB
subtask_1_02.txt AC 14 ms 3968 KB
subtask_1_03.txt AC 104 ms 44660 KB
subtask_1_04.txt AC 92 ms 37948 KB
subtask_1_05.txt AC 93 ms 38844 KB
subtask_1_06.txt AC 80 ms 19388 KB
subtask_1_07.txt AC 88 ms 17152 KB
subtask_1_08.txt AC 94 ms 17280 KB
subtask_1_09.txt AC 219 ms 100720 KB
subtask_1_10.txt WA 14 ms 5632 KB
subtask_1_11.txt WA 17 ms 6144 KB
subtask_1_12.txt AC 1 ms 256 KB
subtask_1_13.txt AC 1 ms 256 KB