제출 #135978

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
135978		IOrtroiii	Simurgh (IOI17_simurgh)	C++14	100 / 100	880 ms	10848 KiB

simurgh

#include "simurgh.h"

#include <bits/stdc++.h>

using namespace std;

int n, m;
vector<pair<int, int>> g[505];
int par[505];
int parId[505];
int high[505];
int color[505 * 505];
vector<int> tree;
int u[505 * 505], v[505 * 505];

struct Dsu {
   int par[505];
   void init() {
      for (int i = 0; i < n; ++i) {
         par[i] = i;
      }
   }
   int find(int u) {
      if (u != par[u]) {
         par[u] = find(par[u]);
      }
      return par[u];
   }
   bool merge(int u, int v) {
      u = find(u);
      v = find(v);
      if (u == v) {
         return false;
      } else {
         par[v] = u;
         return true;
      }
   }
} d;

void dfs(int u) {
   for (auto e : g[u]) {
      int v, id;
      tie(v, id) = e;
      if (v != par[u]) {
         par[v] = u;
         parId[v] = id;
         high[v] = high[u] + 1;
         dfs(v);
      }
   }
}

vector<int> findPath(int u, int v) {
   vector<int> ans;
   while (u != v) {
      if (high[u] > high[v]) {
         ans.emplace_back(parId[u]);
         u = par[u];
      } else {
         ans.emplace_back(parId[v]);
         v = par[v];
      }
   }
   return ans;
}

int get(vector<int> es) {
   d.init();
   for (int i : es) {
      d.merge(u[i], v[i]);
   }
   int offset = 0;
   for (int i : tree) {
      if (d.merge(u[i], v[i])) {
         offset += color[i];
         es.push_back(i);
      }
   }
   assert(es.size() == n - 1);
   return count_common_roads(es) - offset;
}

vector<int> ans;

void solve(int cnt, vector<int> go) {
   int n = go.size();
   if (cnt == 0) {
      return;
   } else if (cnt == n) {
      for (int i : go) {
         ans.emplace_back(i);
      }
      return;
   } else {
      vector<int> lgo = vector<int>(go.begin(), go.begin() + (n / 2));
      vector<int> rgo = vector<int>(go.begin() + (n / 2), go.end());
      int lcnt = get(lgo);
      int rcnt = cnt - lcnt;
      solve(lcnt, lgo);
      solve(rcnt, rgo);
   }
}

vector<int> find_roads(int n, vector<int> u, vector<int> v) {
   ::n = n;
   m = u.size();
	for (int i = 0; i < m; ++i) {
      ::u[i] = u[i];
      ::v[i] = v[i];
      color[i] = -1;
	}
	d.init();
	set<int> out;
	for (int i = 0; i < m; ++i) {
      if (d.merge(u[i], v[i])) {
         tree.push_back(i);
         g[u[i]].emplace_back(v[i], i);
         g[v[i]].emplace_back(u[i], i);
      } else {
         out.insert(i);
      }
	}
	dfs(0);
	for (int i : out) {
      vector<int> cur = findPath(u[i], v[i]);
      bool flag = false;
      for (int j : cur) {
         if (color[j] == -1) {
            flag = true;
         }
      }
      if (!flag) {
         continue;
      }
      cur.emplace_back(i);
      int numEdge = -1;
      for (int j : cur) {
         if (color[j] != -1) {
            vector<int> q;
            for (int k : cur) if (j != k) {
               q.emplace_back(k);
            }
            numEdge = get(q) + color[j];
            break;
         }
      }
      vector<pair<int, int>> vals;
      for (int j : cur) {
         if (color[j] == -1) {
            vector<int> q;
            for (int k : cur) if (j != k) {
               q.emplace_back(k);
            }
            vals.emplace_back(j, get(q));
            numEdge = max(numEdge, vals.back().second);
         }
      }
      for (auto p : vals) {
         color[p.first] = p.second < numEdge;
      }
	}
	for (int i : tree) {
      color[i] = abs(color[i]);
      if (color[i]) {
         ans.emplace_back(i);
      }
	}
	for (int i = 0; i < n; ++i) {
      vector<int> go;
      for (int j : out) {
         if (u[j] == i || v[j] == i) {
            go.emplace_back(j);
         }
      }
      if (go.size()) {
         for (int j : go) {
            out.erase(j);
         }
         solve(get(go), go);
      }
	}
	return ans;
}
// g++ -std=c++14 grader.cpp simurgh.cpp

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

In file included from /usr/include/c++/7/cassert:44:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:33,
                 from simurgh.cpp:3:
simurgh.cpp: In function 'int get(std::vector<int>)':
simurgh.cpp:80:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    assert(es.size() == n - 1);
           ~~~~~~~~~~^~~~~~~~

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