제출 #375612

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
375612		Mamnoon_Siam	Simurgh (IOI17_simurgh)	C++17	51 / 100	516 ms	5484 KiB

simurgh

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

using ii = pair<int, int>;
using vi = vector<int>;
using ll = long long;
#define sz(v) (int)(v).size()
#define all(v) begin(v), end(v)
#define fi first
#define se second
#define pb push_back
#define eb emplace_back

string to_string(string s) {
  return '"' + s + '"';
}

string to_string(const char* s) {
  return to_string((string) s);
}

string to_string(bool b) {
  return (b ? "true" : "false");
}

template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}

void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}

#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

const int N = 1 << 8;
using bs = bitset<N>;

bs g[N], unvis, onstk;
int eid[N][N], n;
bool flag; // have I detected a cyc yet?
int par[N];
bool oncyc[N*N];
vi U, V;
int status[N*N];

void discard(int u, int v) {
  eid[u][v] = eid[v][u] = -1;
  g[u][v] = g[v][u] = 0;
}

void dfs(int u, int dad, vi& cyc, vi& tr) {
  unvis[u] = 0;
  onstk[u] = 1;
  if(!flag) {
    if(~dad) onstk[dad] = 0;
    int back = (int)(g[u] & onstk)._Find_first();
    if(back < n) {
      flag = 1;
      cyc.emplace_back(eid[back][u]);
      int v = u;
      while(v != back) {
        cyc.emplace_back(eid[par[v]][v]);
        v = par[v];
      }
    }
    if(~dad) onstk[dad] = 1;
  }
  while(true) {
    int v = (int)(g[u] & unvis)._Find_first();
    if(v >= n) break;
    par[v] = u;
    tr.emplace_back(eid[u][v]);
    dfs(v, u, cyc, tr);
  }
  onstk[u] = 0;
}

vi find_roads(int _n, vi _U, vi _V) {
  n = _n, U = _U, V = _V;
  memset(status, -1, sizeof status);
  for(int i = 0; i < n; ++i) for(int j = 0; j < n; ++j) eid[i][j] = -1;
  for(int i = 0; i < sz(U); ++i) {
    int u = U[i], v = V[i];
    eid[u][v] = eid[v][u] = i;
    g[u][v] = g[v][u] = 1;
  }

  while(true) {
    unvis.set();
    onstk.reset();
    flag = 0;
    vi cyc, tr;
    dfs(0, -1, cyc, tr);
    if(!flag) break;
    debug(tr);
    debug(cyc);
    for(int i : cyc) oncyc[i] = 1;
    vi r; r.reserve(n);
    for(int i : cyc) r.pb(i);
    for(int i : tr) if(!oncyc[i]) r.pb(i);

    vi rep(sz(cyc), -1);
    int mx = INT_MIN;
    for(int i = 0; i < sz(cyc); ++i) {
      if(~status[cyc[i]]) continue;
      vi rr = r;
      rr.erase(find(all(rr), cyc[i]));
      debug(rr);
      rep[i] = count_common_roads(rr);
      mx = max(mx, rep[i]);
    }
    for(int i = 0; i < sz(cyc); ++i)
      if(!~rep[i]) rep[i] = mx - 1;
    for(int i = 0; i < sz(cyc); ++i) {
      if(rep[i] == mx) {
        debug(cyc[i]);
        discard(U[cyc[i]], V[cyc[i]]);
        status[cyc[i]] = 0;
      } else {
        status[cyc[i]] = 1;
      }
    }
    for(int i : cyc) oncyc[i] = 0;
  }

  set<int> rem_edges;
  for(int i = 0; i < n; ++i)
    for(int j = 0; j < n; ++j)
      if(~eid[i][j]) rem_edges.insert(eid[i][j]);

  return vi(all(rem_edges));

	/*vi r(n - 1);
	for(int i = 0; i < n - 1; i++)
		r[i] = i;
	int common = count_common_roads(r);
	if(common == n - 1)
		return r;
	r[0] = n - 1;
	return r;*/
  return {};
}

컴파일 시 표준 에러 (stderr) 메시지

simurgh.cpp: In function 'vi find_roads(int, vi, vi)':
simurgh.cpp:58:20: warning: statement has no effect [-Wunused-value]
   58 | #define debug(...) 42
      |                    ^~
simurgh.cpp:121:5: note: in expansion of macro 'debug'
  121 |     debug(tr);
      |     ^~~~~
simurgh.cpp:58:20: warning: statement has no effect [-Wunused-value]
   58 | #define debug(...) 42
      |                    ^~
simurgh.cpp:122:5: note: in expansion of macro 'debug'
  122 |     debug(cyc);
      |     ^~~~~
simurgh.cpp:58:20: warning: statement has no effect [-Wunused-value]
   58 | #define debug(...) 42
      |                    ^~
simurgh.cpp:134:7: note: in expansion of macro 'debug'
  134 |       debug(rr);
      |       ^~~~~
simurgh.cpp:58:20: warning: statement has no effect [-Wunused-value]
   58 | #define debug(...) 42
      |                    ^~
simurgh.cpp:142:9: note: in expansion of macro 'debug'
  142 |         debug(cyc[i]);
      |         ^~~~~

• Subtask 1: 13 / 13
• Subtask 2: 17 / 17
• Subtask 3: 21 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 30