Submission #201423

#	Time	Username	Problem	Language	Result	Execution time	Memory
201423		BThero	Meetings (JOI19_meetings)	C++17	100 / 100	904 ms	2712 KiB

meetings

// Why am I so dumb? :c
// chrono::system_clock::now().time_since_epoch().count()
                                                  
#include<bits/stdc++.h>
#include "meetings.h"
//#include<ext/pb_ds/assoc_container.hpp>
//#include<ext/pb_ds/tree_policy.hpp>

#define pb push_back
#define mp make_pair

#define all(x) (x).begin(), (x).end()

#define fi first
#define se second

using namespace std;
//using namespace __gnu_pbds;

typedef long long ll;   
typedef pair<int, int> pii;
//template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());

struct cmp {
    int x;

    cmp(int y) {
        x = y;        
    }

    bool operator()(int a, int b) {
        return Query(x, a, b) == a;
    }
};

int n;

void dfs(vector<int> S) {
    if (S.size() <= 1) {
        return;
    }

    int a = S[0];
    int b = S[1 + rnd() % (S.size() - 1)];
    vector<int> path;
    vector<vector<int> > later(n + 1);
    path.pb(a);
    path.pb(b);

    for (int c : S) {
        if (c == a || c == b) {
            continue;
        }

        int x = Query(a, b, c);

        if (x == c) {
            path.pb(c);            
        }
        else {
            later[x].pb(c);        
        }                                                                                                                                                                 
    }    

    sort(path.begin() + 1, path.end(), cmp(a));

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

        if (a > b) {
            swap(a, b);
        }

        Bridge(a, b);
    }

    for (int c : S) {
        later[c].insert(later[c].begin(), c);
        dfs(later[c]);
    }                                                                                        
}

void Solve(int N) {
    n = N;
    vector<int> v;

    for (int i = 0; i < n; ++i) {
        v.pb(i);
    }

    dfs(v);
}

Compilation message (stderr)

meetings.cpp: In function 'void dfs(std::vector<int>)':
meetings.cpp:69:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 1; i < path.size(); ++i) {
                     ~~^~~~~~~~~~~~~

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