Submission #904843

#	Time	Username	Problem	Language	Result	Execution time	Memory
904843		406	Meetings (JOI19_meetings)	C++17	100 / 100	739 ms	1064 KiB

meetings

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

void bridge(int u, int v) {
        if (u > v) swap(u, v);
        assert(u != v);
        Bridge(u, v);
}

void solve(vector<int> &T) {
        if (T.size() <= 1) 
                return;
        if (T.size() == 2) {
                bridge(T[0], T[1]);
                return;
        }
        assert(T[0] != T[1]);
        vector<int> path;
        map<int, vector<int>> S;

        for (int i = 2; i < T.size(); ++i) {
                int q = Query(T[0], T[1], T[i]);
                if (q != T[0] && q != T[1]) 
                        path.push_back(q);
                S[q].push_back(T[i]);
        }
        sort(path.begin(), path.end());
        path.resize(unique(path.begin(), path.end()) - path.begin());

        sort(path.begin(), path.end(), [&](int u, int v) {return Query(T[0], u, v) == u;});
        path.insert(path.begin(), T[0]);
        path.push_back(T[1]);

        for (int i = 1; i < path.size(); ++i)
                bridge(path[i], path[i - 1]);

        S[T[0]].push_back(T[0]);
        S[T[1]].push_back(T[1]);
        for (auto [u, T0]: S) solve(T0);
}

void Solve(int32_t n){
        srand(time(NULL));
        vector<int> nodes(n);
        iota(nodes.begin(), nodes.end(), 0);
        mt19937 rng((int64_t) new char);
        shuffle(nodes.begin(), nodes.end(), rng);

        solve(nodes);
}

Compilation message (stderr)

meetings.cpp: In function 'void solve(std::vector<int>&)':
meetings.cpp:22:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |         for (int i = 2; i < T.size(); ++i) {
      |                         ~~^~~~~~~~~~
meetings.cpp:35:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |         for (int i = 1; i < path.size(); ++i)
      |                         ~~^~~~~~~~~~~~~

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