Submission #814796

#	Time	Username	Problem	Language	Result	Execution time	Memory
814796		LucaIlie	Meetings (JOI19_meetings)	C++17	100 / 100	905 ms	768 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>

using namespace std;

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

void solve( int root, vector<int> &subtree ) {
    if ( subtree.size() == 0 )
        return;

    random_shuffle( subtree.begin(), subtree.end() );
    unordered_map<int, vector<int>> newSubtrees;
    vector<int> path;

    int pivot = subtree[0];
    for ( int i = 1; i < subtree.size(); i++ ) {
        int ans = Query( root, pivot, subtree[i] );
        if ( ans == subtree[i] )
            path.push_back( subtree[i] );
        else
            newSubtrees[ans].push_back( subtree[i] );
    }

    for ( int i = 1; i < path.size(); i++ ) {
        int l = -1, r = i;
        while ( r - l > 1 ) {
            int mid = (l + r) / 2;
            if ( Query( root, path[mid], path[i] ) == path[mid] )
                l = mid;
            else
                r = mid;
        }
        for ( int j = i; j > r; j-- )
            swap( path[j], path[j - 1] );
    }


    if ( path.size() == 0 )
        bridge( root, pivot );
    else {
        bridge( root, path[0] );
        for ( int i = 0; i < path.size() - 1; i++ )
            bridge( path[i], path[i + 1] );
        bridge( path[path.size() - 1], pivot );
    }

    for ( auto &st: newSubtrees )
        solve( st.first, st.second );
}

void Solve( int n ) {
    int root = 0;
    vector<int> subtree;
    for ( int u = 1; u < n; u++ )
        subtree.push_back( u );
    solve( root, subtree );
}

Compilation message (stderr)

meetings.cpp: In function 'void solve(int, std::vector<int>&)':
meetings.cpp:21:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     for ( int i = 1; i < subtree.size(); i++ ) {
      |                      ~~^~~~~~~~~~~~~~~~
meetings.cpp:29:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for ( int i = 1; i < path.size(); i++ ) {
      |                      ~~^~~~~~~~~~~~~
meetings.cpp:47:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |         for ( int i = 0; i < path.size() - 1; i++ )
      |                          ~~^~~~~~~~~~~~~~~~~

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