Submission #840155

#	Time	Username	Problem	Language	Result	Execution time	Memory
840155		happypotato	Longest Trip (IOI23_longesttrip)	C++17	60 / 100	295 ms	780 KiB

longesttrip

#include "longesttrip.h"
 
#include <bits/stdc++.h>
#pragma GCC optimize("O2")
using namespace std;
// #define int long long // remove when necessary
#define pii pair<int, int>
#define ff first
#define ss second
#define pb push_back
#define ll long long
const int mxN = 256;
vector<int> adj[mxN];
vector<int> grp[mxN];
int conn[mxN][mxN];
bool con(int x, int y) {
    if (conn[x][y] != -1) return conn[x][y];
    return (conn[x][y] = conn[y][x] = are_connected({x}, {y}));
}
int n;
int dsupp[mxN];
vector<int> nxt[mxN];
bool vis[mxN];
void resetvis() {
  for (int i = 0; i < n; i++) vis[i] = false;
}
void reset() {
  for (int i = 0; i < n; i++) {
    adj[i].clear();
    grp[i].clear();
    for (int j = 0; j < n; j++) {
      conn[i][j] = -1;
    }
    dsupp[i] = i;
    nxt[i].clear();
    vis[i] = false;
  }
}
int DSUFind(int u) {
  if (dsupp[u] == u) return u;
  return (dsupp[u] = DSUFind(dsupp[u]));
}
void DSUMerge(int u, int v) {
  u = DSUFind(u); v = DSUFind(v);
  if (u != v) dsupp[v] = u;
}
vector<int> GetPath(int st) {
  resetvis();
  vector<int> res;
  while (true) {
    res.pb(st);
    vis[st] = true;
    bool found = false;
    for (int &v : nxt[st]) {
      if (!vis[v]) {
        st = v;
        found = true;
        break;
      }
    }
    if (!found) break;
  }
  return res;
}
vector<int> MakePath(vector<int> &v) {
  if (v.size() == 1) return {v[0]};
  if (v.size() == 2) {
    if (con(v[0], v[1])) return {v[0], v[1]};
    else return {v[0]};
  }
  if (v.size() == 3) {
    if (con(v[0], v[1]) && con(v[0], v[2])) return {v[1], v[0], v[2]};
    if (con(v[0], v[1]) && con(v[1], v[2])) return {v[0], v[1], v[2]};
    if (con(v[0], v[2]) && con(v[1], v[2])) return {v[0], v[2], v[1]};
    if (con(v[0], v[1])) return {v[0], v[1]};
    if (con(v[0], v[2])) return {v[0], v[2]};
    if (con(v[1], v[2])) return {v[1], v[2]};
    return {v[0]};
  }
  for (int i = 0; i < n; i++) {
    nxt[i].clear();
  }
  pair<pii, pii> cur = {{v[0], v[0]}, {v[1], v[1]}};
  for (int i = 2; i < (int)(v.size()); i++) {
    if (con(cur.ff.ff, cur.ss.ff)) {
      nxt[cur.ff.ff].pb(cur.ss.ff);
      nxt[cur.ss.ff].pb(cur.ff.ff);
      cur.ff.ff = cur.ss.ss;
      cur.ss = {v[i], v[i]};
    } else if (con(cur.ff.ff, v[i])) {
      nxt[cur.ff.ff].pb(v[i]);
      nxt[v[i]].pb(cur.ff.ff);
      cur.ff.ff = v[i];
    } else {
      conn[cur.ss.ff][v[i]] = conn[v[i]][cur.ss.ff] = 1;
      nxt[cur.ss.ff].pb(v[i]);
      nxt[v[i]].pb(cur.ss.ff);
      cur.ss.ff = v[i];
    }
  }
  int st;
  if (con(cur.ff.ff, cur.ss.ff)) {
    nxt[cur.ff.ff].pb(cur.ss.ff);
    nxt[cur.ss.ff].pb(cur.ff.ff);
    st = cur.ff.ss;
  } else if (con(cur.ff.ff, cur.ss.ss)) {
    nxt[cur.ff.ff].pb(cur.ss.ss);
    nxt[cur.ss.ss].pb(cur.ff.ff);
    st = cur.ff.ss;
  } else if (con(cur.ff.ss, cur.ss.ff)) {
    nxt[cur.ff.ss].pb(cur.ss.ff);
    nxt[cur.ss.ff].pb(cur.ff.ss);
    st = cur.ff.ff;
  } else if (con(cur.ff.ss, cur.ss.ss)) {
    nxt[cur.ff.ss].pb(cur.ss.ss);
    nxt[cur.ss.ss].pb(cur.ff.ss);
    st = cur.ff.ff;
  } else {
    vector<int> res[2];
    res[0] = GetPath(cur.ff.ff);
    res[1] = GetPath(cur.ss.ff);
 
    // cerr << "res0: ";
    // for (int &x : res[0]) cerr << x << ' ';
    // cerr << endl;
    // cerr << "res1: ";
    // for (int &x : res[1]) cerr << x << ' ';
    // cerr << endl;
 
    bool found = false;
    for (int i = 0; i < (int)(res[0].size()); i++) {
      for (int j = 0; j < (int)(res[1].size()); j++) {
        if (con(res[0][i], res[1][j])) {
          // cerr << "FOUND " << res[0][i] << ' ' << res[1][j] << endl;
          nxt[res[0][i]].pb(res[1][j]);
          nxt[res[1][j]].pb(res[0][i]);
 
          if (res[0].size() >= 3) {
            nxt[cur.ff.ff].pb(cur.ff.ss);
            nxt[cur.ff.ss].pb(cur.ff.ff);
            // cerr << "RES0 ";
            // for (int &x : res[0]) cerr << x << ' ';
            // cerr << endl;
            st = (i == 0 ? res[0].back() : res[0][i - 1]);
            // cerr << "ST " << st << endl;
            vector<int>::iterator it;
            for (it = nxt[st].begin(); it != nxt[st].end(); ++it) {
              if (*it == res[0][i]) {
                nxt[st].erase(it);
                break;
              }
            }
            for (it = nxt[res[0][i]].begin(); it != nxt[res[0][i]].end(); ++it) {
              if (*it == st) {
                nxt[res[0][i]].erase(it);
                break;
              }
            }
          } else {
            st = (res[0].size() == 2 ? res[0][i ^ 1] : res[0][i]);
          }
 
          if (res[1].size() >= 3) {
            nxt[cur.ss.ff].pb(cur.ss.ss);
            nxt[cur.ss.ss].pb(cur.ss.ff);
            int tar = (j == 0 ? res[1].back() : res[1][j + 1]);
            vector<int>::iterator it;
            for (it = nxt[tar].begin(); it != nxt[tar].end(); ++it) {
              if (*it == res[1][j]) {
                nxt[tar].erase(it);
                break;
              }
            }
            for (it = nxt[res[1][j]].begin(); it != nxt[res[1][j]].end(); ++it) {
              if (*it == tar) {
                nxt[res[1][j]].erase(it);
                break;
              }
            }
          }
 
          found = true;
          break;
        }
      }
      if (found) break;
    }
    if (!found) {
      while (true) continue;
    }
  }
 
  // cerr << "find path for: ";
  // for (int &x : v) cerr << x << ' ';
  // cerr << endl;
  
  vector<int> res = GetPath(st);
 
  // cerr << "st: " << st << endl;
  // cerr << "result: ";
  // for (int &x : res) cerr << x << ' ';
  // cerr << endl;
 
  return res;
}
vector<int> longest_trip(int N, int D)
{
  n = N;
  reset();
  if (D == 3) {
    vector<int> res(n);
    for (int i = 0; i < n; i++) res[i] = i;
    return res;
  }
  
  queue<int> q;
  for (int i = 0; i < n; i++) {
     grp[i].pb(i);
     q.push(i);
  }
  while (q.size() >= 3) {
     int a = q.front(); q.pop();
     int b = q.front(); q.pop();
     int c = q.front(); q.pop();
     if (are_connected(grp[a], grp[b])) {
         DSUMerge(a, b);
         for (int &x : grp[b]) grp[a].pb(x);
         grp[b].clear();
         q.push(a);
         q.push(c);
     } else if (are_connected(grp[a], grp[c])) {
         DSUMerge(a, c);
         for (int &x : grp[c]) grp[a].pb(x);
         grp[c].clear();
         q.push(a);
         q.push(b);
     } else {
         DSUMerge(b, c);
         for (int &x : grp[c]) grp[b].pb(x);
         grp[c].clear();
         q.push(a);
         q.push(b);
     }
  }
  int fina = q.front(); q.pop();
  int finb = q.front(); q.pop();
  if (are_connected(grp[fina], grp[finb])) {
      DSUMerge(fina, finb);
      for (int &x : grp[finb]) grp[fina].pb(x);
      grp[finb].clear();
  }
  
  vector<int> best = {};
  for (int i = 0; i < n; i++) {
    if (grp[i].empty()) continue;
    vector<int> res = MakePath(grp[i]);
    if (res.size() > best.size()) {
      best = res;
    }
  }
  return best;
}

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 25 / 25
• Subtask 4: 19.999999998 / 60