Submission #205394

#	Time	Username	Problem	Language	Result	Execution time	Memory
205394		extraterrestrial	Arranging Tickets (JOI17_arranging_tickets)	C++14	0 / 100	5 ms	376 KiB

arranging_tickets

#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;
#define F first
#define S second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define SZ(x) (int)(x).size()
#define int ll

const int INF = 1e9 + 10;
const ll BINF = 1e18 + 10;
struct Flow {
  struct edge {
    int to, c, w, f;
  };
  vector<edge> arr;
  vector<vector<int>> g;
  vector<int> pnt;
  vector<ll> potential;
  vector<bool> used;
  int n, m, s, t, cnt = 0;
  Flow(int maxn, int maxm, int _s, int _t) {
    n = maxn;
    m = maxm;
    s = _s;
    t = _t;
    arr.resize(m + 1);
    g.resize(n + 1);
    pnt.resize(n + 1);
    potential.resize(n + 1);
    used.resize(n + 1);
  }
  inline void add_edge(int from, int to, int c, int w = 0, int f = 0) {
    arr[cnt] = {to, c, w, f};
    g[from].pb(cnt++);
  }
  int Ford_Fulkerson_dfs(int v, int min_f, int need = 1) {
    if (v == t) {
      return min_f;
    }
    used[v] = true;
    for (int u : g[v]) {
      if (!used[arr[u].to] && arr[u].c - arr[u].f >= need) {
        int val = Ford_Fulkerson_dfs(arr[u].to, min(min_f, arr[u].c - arr[u].f), need);
        if (val >= need) {
          arr[u].f += val;
          arr[u ^ 1].f -= val;
          return val;
        }
      }
    }
    return 0;
  }
  inline int Ford_Fulkerson() { //O(|F| * E)
    int res = 0;
    for (;;) {
      fill(all(used), false);
      int val = Ford_Fulkerson_dfs(s, INF);
      if (!val) {
        return res;
      }
      res += val;
    }
  }
  inline int Ford_Fulkerson_with_scaling(int mx = INF) { //O(E^2 * log(U)), where U is the maximum capacity
    int res = 0, up = (int)log2(mx);
    for (int k = up; k >= 0; k--) {
      for (;;) {
        fill(all(used), false);
        int val = Ford_Fulkerson_dfs(s, INF, 1 << k);
        if (!val) {
          break;
        }
        res += val;
      }
    }
    return res;
  }
  inline int Edmonds_Karp_bfs(int need = 1) {
    vector<pair<int, int>> from(n + 1);
    fill(all(used), false);
    queue<int> q;
    q.push(s);
    while (!q.empty()) {
      int v = q.front();
      q.pop();
      for (int u : g[v]) {
        if (arr[u].c - arr[u].f >= need && !used[arr[u].to]) {
          used[arr[u].to] = true;
          q.push(arr[u].to);
          from[arr[u].to] = {v, u};
        }
      }
    }
    if (!used[t]) {
      return 0;
    }
    int now = t, min_f = INF;
    while (now != s) {
      min_f = min(min_f, arr[from[now].second].c - arr[from[now].second].f);
      now = from[now].first;
    }
    now = t;
    while (now != s) {
      int ind = from[now].second;
      arr[ind].f += min_f;
      arr[ind ^ 1].f -= min_f;
      now = from[now].first;
    }
    return min_f;
  }
  int Edmonds_Karp() { //O(VE^2)
    int res = 0;
    for (;;) {
      int val = Edmonds_Karp_bfs();
      if (!val) {
        return res;
      }
      res += val;
    }
  }
  int Edmonds_Karp_with_scaling(int mx = INF) { // O(E^2 * log(U)), where U is the maximum capacity
    int res = 0, up = (int)log2(mx);
    for (int k = up; k >= 0; k--) {
      for (;;) {
        int val = Edmonds_Karp_bfs(1 << k);
        if (!val) {
          break;
        }
        res += val;
      }
    }
    return res;
  }
  int Dinic_dfs(int v, int min_f, int need = 1) {
    if (v == t) {
      return min_f;
    }
    used[v] = true;
    for (; pnt[v] < SZ(g[v]); pnt[v]++) {
      int u = g[v][pnt[v]];
      if (!used[arr[u].to] && arr[u].c - arr[u].f >= need) {
        int val = Dinic_dfs(arr[u].to, min(min_f, arr[u].c - arr[u].f), need);
        if (val >= need) {
          arr[u].f += val;
          arr[u ^ 1].f -= val;
          return val;
        }
      }
    }
    return 0;
  }
  inline int Dinic_bfs(int need = 1) {
    vector<int> dist(n + 1, INF);
    dist[s] = 0;
    queue<int> q;
    q.push(s);
    while (!q.empty()) {
      int v = q.front();
      q.pop();
      for (auto u : g[v]) {
        if (arr[u].c - arr[u].f >= need && dist[arr[u].to] == INF) {
          dist[arr[u].to] = dist[v] + 1;
          q.push(arr[u].to);
        }
      }
    }
    if (dist[t] == INF) {
      return 0;
    }
    fill(all(pnt), 0);
    int res = 0;
    for (;;) {
      fill(all(used), false);
      int val = Dinic_dfs(s, INF, need);
      if (!val) {
        return res;
      }
      res += val;
    }
  }
  int Dinic() { // O(V^2 * E), on single networks O(E * sqrt(E))
    int res = 0;
    for (;;) {
      int val = Dinic_bfs();
      if (!val) {
        return res;
      }
      res += val;
    }
  }
  int Dinic_with_scaling(int mx = INF) { // O(VE * log(U)), where U is the maximum capacity
    int res = 0, up = (int)log2(mx);
    for (int k = up; k >= 0; k--) {
      for (;;) {
        int val = Dinic_bfs(1 << k);
        if (!val) {
          break;
        }
        res += val;
      }
    }
    return res;
  }
  inline ll Ford_Bellman() {
    vector<ll> dist(n + 1, INF);
    vector<pair<int, int>> from(n + 1);
    vector<bool> already(n + 1, false);
    dist[s] = 0;
    queue<int> q;
    q.push(s);
    while (!q.empty()) {
      int v = q.front();
      q.pop();
      already[v] = false;
      for (auto it : g[v]) {
        if (dist[v] + arr[it].w < dist[arr[it].to] && arr[it].c > arr[it].f) {
          dist[arr[it].to] = dist[v] + arr[it].w;
          from[arr[it].to] = {v, it};
          if (!already[arr[it].to]) {
            q.push(arr[it].to);
            already[arr[it].to] = true;
          }
        }
      }
    }
    int now = t, mn = INF;
    while (from[now].first) {
      mn = min(mn, arr[from[now].second].c - arr[from[now].second].f);
      now = from[now].first;
    }
    now = t;
    while (from[now].first) {
      arr[from[now].second].f += mn;
      arr[from[now].second ^ 1].f -= mn;
      now = from[now].first;
    }
    return dist[t] * mn;
  }
  void init_potentials() {
    vector<ll> dist(n + 1, INF);
    vector<bool> already(n + 1, false);
    dist[s] = 0;
    queue<int> q;
    q.push(s);
    while (!q.empty()) {
      int v = q.front();
      q.pop();
      already[v] = false;
      for (auto it : g[v]) {
        if (dist[v] + arr[it].w < dist[arr[it].to] && arr[it].c > arr[it].f) {
          dist[arr[it].to] = dist[v] + arr[it].w;
          if (!already[arr[it].to]) {
            q.push(arr[it].to);
            already[arr[it].to] = true;
          }
        }
      }
    }
    for (int i = 1; i <= n; i++) {
      if (dist[i] != INF) {
        potential[i] = dist[i];
      }
    }
  }
  inline ll Dijkstra_with_potentials1() {
    vector<ll> dist(n + 1, INF);
    vector<pair<int, int>> from(n + 1);
    dist[s] = 0;
    set<pair<ll, int>> st;
    for (int i = 1; i <= n; i++) {
      st.insert({dist[i], i});
    }
    while (!st.empty()) {
      int v = st.begin()->second;
      st.erase(st.begin());
      for (auto it : g[v]) {
        int u = arr[it].to;
        ll cost = arr[it].w + potential[v] - potential[u];
        if (arr[it].f < arr[it].c && dist[v] + cost < dist[u]) {
          st.erase({dist[u], u});
          dist[u] = dist[v] + cost;
          st.insert({dist[u], u});
          from[u] = {v, it};
        }
      }
    }
    int now = t, mn = INF;
    while (from[now].first) {
      mn = min(mn, arr[from[now].second].c - arr[from[now].second].f);
      now = from[now].first;
    }
    now = t;
    while (from[now].first) {
      arr[from[now].second].f += mn;
      arr[from[now].second ^ 1].f -= mn;
      now = from[now].first;
    }
    ll res = (dist[t] - potential[s] + potential[t]) * mn;
    for (int i = 1; i <= n; i++) {
      if (dist[i] < INF) {
        potential[i] += dist[i];
      }
    }
    return res;
  }
  inline ll Dijkstra_with_potentials2() {
    vector<ll> dist(n + 1, INF);
    vector<pair<int, int>> from(n + 1);
    fill(all(used), false);
    dist[s] = 0;
    for (int i = 1; i <= n; i++) {
      pair<int, int> best = {INF, INF};
      for (int j = 1; j <= n; j++) {
        if (!used[j]) {
          best = min(best, {dist[j], j});
        }
      }
      int v = best.second;
      used[v] = true;
      for (auto it : g[v]) {
        int u = arr[it].to;
        ll cost = arr[it].w + potential[v] - potential[u];
        if (arr[it].f < arr[it].c && dist[v] + cost < dist[u]) {
          dist[u] = dist[v] + cost;
          from[u] = {v, it};
        }
      }
    }
    int now = t, mn = INF;
    while (from[now].first) {
      mn = min(mn, arr[from[now].second].c - arr[from[now].second].f);
      now = from[now].first;
    }
    now = t;
    while (from[now].first) {
      arr[from[now].second].f += mn;
      arr[from[now].second ^ 1].f -= mn;
      now = from[now].first;
    }
    ll res = (dist[t] - potential[s] + potential[t]) * mn;
    for (int i = 1; i <= n; i++) {
      if (dist[i] < INF) {
        potential[i] += dist[i];
      }
    }
    return res;
  }
  ll mincost_with_FB(int flow_sz = INF) { // O(|F| * VE)
    ll res = 0;
    for (int i = 0; i < flow_sz; i++) {
      ll val = Ford_Bellman();
      if (val >= BINF) {
        return res;
      }
      res += val;
    }
    return res;
  }
  ll mincost_with_Dijkstra1(int flow_sz = INF) {// O(|F| * E log V)
    init_potentials();
    ll res = 0;
    for (int i = 0; i < flow_sz; i++) {
      ll val = Dijkstra_with_potentials1();
      if (val >= BINF) {
        return res;
      }
      res += val;
    }
    return res;
  }
  ll mincost_with_Dijkstra2(int flow_sz = INF) { // O(|F| * V^2)
    init_potentials();
    ll res = 0;
    for (int i = 0; i < flow_sz; i++) {
      ll val = Dijkstra_with_potentials2();
      if (val >= BINF) {
        return res;
      }
      res += val;
    }
    return res;
  }
};

const int N = 2e5 + 10;
int a[N], b[N], c[N], cap_in[N], cap_out[N];

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
	int n, m;
  cin >> n >> m;
  map<pair<int, int>, int> edge;
  int sum = 0;
  for (int i = 1; i <= m; i++) {
    cin >> a[i] >> b[i] >> c[i];
    if (a[i] > b[i]) {
      swap(a[i], b[i]);
    }
    sum += c[i];
    cap_in[a[i]] += c[i];
    cap_out[b[i]] += c[i];
    edge[{a[i], b[i]}] += c[i];
  }
  int ptr = 0;
  for (auto it : edge) {
    a[++ptr] = it.F.F;
    b[ptr] = it.F.S;
    c[ptr] = it.S;
  }
  m = ptr;
  int add = 0;
  for (int i = 1; i <= n; i++) {
    if (cap_in[i]) {
      add++;
    }
    if (cap_out[i]) {
      add++;
    }
  }
  int l = 0, r = n;
  while (r - l > 1) {
    int mid = (l + r) / 2;
    Flow F(n + 2, 2 * (2 * n + m + add), n + 1, n + 2);
    for (int i = 1; i <= n; i++) {
      if (cap_in[i]) {
        F.add_edge(n + 1, i, cap_in[i]);
        F.add_edge(i, n + 1, 0);
      }
      if (cap_out[i]) {
        F.add_edge(i, n + 2, cap_out[i]);
        F.add_edge(n + 2, i, 0);
      }
    }
    for (int i = 1; i <= n; i++) {
      int to = i + 1;
      if (to == n + 1) {
        to = 1;
      }
      F.add_edge(i, to, mid);
      F.add_edge(to, i, 0);
      F.add_edge(to, i, mid);
      F.add_edge(i, to, 0);
    }
    if (F.Ford_Fulkerson() == sum) {
      r = mid;
    }
    else {
      l = mid;
    }
  } 
  cout << r << '\n'; 
} 

• Subtask 1: 0 / 10
• Subtask 2: 0 / 35
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 15