oj.uz

Submission #131125

# Submission time Handle Problem Language Result Execution time Memory
131125 2019-07-16T15:23:40 Z IOrtroiii Meetings (JOI19_meetings) C++14
0 / 100
 657 ms 776 KB 
#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> all(n - 1);
   iota(all.begin(), all.end(), 1);
   go(0, all);
   cout << "Test\n";
}

Compilation message

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
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB DO NOT PRINT ANYTHING TO STANDARD OUTPUT
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB DO NOT PRINT ANYTHING TO STANDARD OUTPUT
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB DO NOT PRINT ANYTHING TO STANDARD OUTPUT
2 Halted 0 ms 0 KB -

Subtask #4
0 / 71.0

# Verdict Execution time Memory Grader output
1 Incorrect 657 ms 776 KB DO NOT PRINT ANYTHING TO STANDARD OUTPUT
2 Halted 0 ms 0 KB -