Submission #260269

#	Time	Username	Problem	Language	Result	Execution time	Memory
260269		infinitepro	Meetings (JOI19_meetings)	C++17	100 / 100	1223 ms	3192 KiB

meetings

#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC optimization ("Ofast")
#include<bits/stdc++.h>
#include"meetings.h"
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;

#define INF INT_MAX
#define MOD 1000000007
#define all(x) x.begin(), x.end()

map<ii, int> qr;
int ask(int u, int v){
    if(u>v)swap(u,v);
    if(u==v)return u;
    if(qr.find({u,v}) == qr.end())
        qr[{u,v}] = Query(0, u, v);
    return qr[{u,v}];
}

vi sol;
void doit(int root, vi S){
    unordered_map<int, vi> tmp;
    vi path;

    int u = S[rand()%S.size()];
    for(auto v : S){
        int p = ask(u, v);
        if(p == v) path.push_back(v);
        else tmp[p].push_back(v);
    }

    sort(all(path), [&](int a, int b){
        return (ask(a, b) == a);
    });
    for(int x = 1; x < path.size(); x++){
        sol[path[x]] = path[x-1];
    }
    sol[path[0]] = root;

    for(auto [rt, s] : tmp){
        doit(rt, s);
    }
    return;
}

void Solve(int N){
    vi S; sol.resize(N);
    for(int x = 1; x < N; x++)
        S.push_back(x);
    doit(0, S);

    for(int x = 1; x < N; x++)
        Bridge(min(sol[x], x), max(sol[x], x));
    
}

Compilation message (stderr)

meetings.cpp:2:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("O3")
 
meetings.cpp:3:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("unroll-loops")
 
meetings.cpp:4:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("Ofast")
 
meetings.cpp: In function 'void doit(int, vi)':
meetings.cpp:47:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int x = 1; x < path.size(); x++){
                    ~~^~~~~~~~~~~~~

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