Submission #131126

#	Time	Username	Problem	Language	Result	Execution time	Memory
131126		IOrtroiii	Meetings (JOI19_meetings)	C++14	100 / 100	1595 ms	1068 KiB

meetings

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

mt19937 rng(10072002);

void addEdge(int u, int v) {
   if (u > v) swap(u, v);
   Bridge(u, v);
}

void go(int from, vector<int> comp) {
   int id = rng() % (comp.size());
   int to = comp[id];
   swap(comp[id], comp.back());
   comp.pop_back();
   vector<int> path;
   vector<pair<int, int>> vals;
   for (int v : comp) {
      int u = Query(from, to, v);
      if (u == v) {
         path.push_back(v);
      } else {
         vals.emplace_back(u, v);
      }
   }
   if (path.empty()) {
      addEdge(from, to);
   } else {
      sort(path.begin(), path.end(), [&](int x, int y) {
         return Query(from, x, y) == x;
      });
      addEdge(from, path[0]);
      for (int i = 0; i + 1 < path.size(); ++i) {
         addEdge(path[i], path[i + 1]);
      }
      addEdge(path.back(), to);
   }
   sort(vals.begin(), vals.end());
   int l = 0;
   while (l < vals.size()) {
      vector<int> ncomp;
      int r = l;
      while (r < vals.size() && vals[l].first == vals[r].first) {
         ncomp.push_back(vals[r++].second);
      }
      go(vals[l].first, ncomp);
      l = r;
   }
}

void Solve(int n) {
   vector<int> comp(n - 1);
   iota(comp.begin(), comp.end(), 1);
   go(0, comp);
}

Compilation message (stderr)

meetings.cpp: In function 'void go(int, std::vector<int>)':
meetings.cpp:34:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (int i = 0; i + 1 < path.size(); ++i) {
                       ~~~~~~^~~~~~~~~~~~~
meetings.cpp:41:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while (l < vals.size()) {
           ~~^~~~~~~~~~~~~
meetings.cpp:44:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       while (r < vals.size() && vals[l].first == vals[r].first) {
              ~~^~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 10 / 10
• Subtask 3: 12 / 12
• Subtask 4: 71 / 71