Submission #262198

#	Time	Username	Problem	Language	Result	Execution time	Memory
262198		doowey	Meetings (JOI19_meetings)	C++14	100 / 100	1196 ms	16892 KiB

meetings

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

using namespace std;

typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

int n;

const int MAXN = 2020;
int par[MAXN];
int sol[MAXN][MAXN];

int get(int i, int j){
    if(i==j) return i;
    if(sol[i][j] != -1) return sol[i][j];
    return sol[i][j]=sol[j][i]=Query(0, i, j);
}

vector<int> Q[MAXN];
bool has[MAXN];

void dfs(int root, vector<int> oc){
    vector<int> path;
    int res;
    random_shuffle(oc.begin(), oc.end());
    int node = oc[0];
    for(auto x : oc){
        res = get(node, x);
        if(res == x){
            if(!has[x]){
                path.push_back(x);
                has[x]=true;
            }
        }
        else{
            Q[res].push_back(x);
        }
    }
    sort(path.begin(), path.end(), [&](int a, int b){return get(a, b)==a;});
    par[path[0]] = root;
    for(int i = 1; i < path.size(); i ++ )
        par[path[i]] = path[i - 1];
    vector<pair<int, vector<int>>> shit;
    for(auto x : oc){
        if(Q[x].size() > 0){
            shit.push_back(mp(x, Q[x]));
            Q[x].clear();
        }
        has[x]=false;
    }
    if(Q[root].size() > 0){
        shit.push_back(mp(root, Q[root]));
        Q[root].clear();
    }
    for(auto p : shit)
        dfs(p.fi, p.se);
}

void Solve(int CN){
    n = CN;
    for(int i = 1; i < n ; i ++ )
        par[i] = -1;
    for(int i = 0 ; i < n ; i ++ ){
        for(int j = 0 ; j < n ; j ++ ){
            sol[i][j]=-1;
        }
    }
    vector<int> ord;
    for(int i = 1; i < n; i ++ )
        ord.push_back(i);
    random_shuffle(ord.begin(), ord.end());
    dfs(0, ord);
    int x, y;
    for(int i = 1; i < n; i ++ ){
        x = i;
        y = par[i];
        if(x > y) swap(x, y);
        Bridge(x, y);
    }
}

Compilation message (stderr)

meetings.cpp: In function 'void dfs(int, std::vector<int>)':
meetings.cpp:47:22: 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 = 1; i < path.size(); i ++ )
      |                    ~~^~~~~~~~~~~~~

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