Submission #201561

#	Time	Username	Problem	Language	Result	Execution time	Memory
201561		Rakhmand	Meetings (JOI19_meetings)	C++14	100 / 100	1418 ms	3196 KiB

meetings

#include "meetings.h"

#include <cstring>
#include <list>
#include <map>
#include <deque>
#include <stack>
#include <bitset>
#include <functional>
#include <numeric>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <queue>
#include <cmath>
#include <ctime>
#include <cassert>
#include <iterator>

using namespace std;

int n;
int batya;
vector<pair<int, int> > ans;

bool cmp(int x, int y){
    if(y == batya){
        return 0;
    }
    if(x == batya){
        return 1;
    }
    if(Query(batya, x, y) == x) return 1;
    else return 0;
}

void dfs(vector<int> v){
    if(v.size() <= 1){
        return ;
    }
    vector<int> path;
    vector<vector<int> > lol(n);
    int a = v[v.size() - 1];
    int b = v[rand() %  (v.size() - 1)];
    path.push_back(a);
    path.push_back(b);
    for(int i = 0; i < v.size(); i++){
        int x = v[i];
        if(x == a || x == b) continue;
        int c = Query(a, b, x);
        if(c == x){
            path.push_back(c);
        }else{
            lol[c].push_back(x);
        }
    }
    batya = a;
    sort(path.begin(), path.end(), cmp);
    for(int i = 1; i < path.size(); i++){
        ans.push_back({path[i], path[i - 1]});
    }
    for(int i = 0; i < v.size(); i++){
        int x = v[i];
        lol[x].push_back(x);
        dfs(lol[x]);
    }
}

void Solve(int N) {
    n = N;
    srand(time(NULL));
    vector<int> v;
    for(int i = 0; i < N; i++) v.push_back(i);
    dfs(v);
    for(int i = 0; i < ans.size(); i++){
        int x = ans[i].first, y = ans[i].second;
        if(x > y) swap(x, y);
        Bridge(x, y);
    }
}

Compilation message (stderr)

meetings.cpp: In function 'void dfs(std::vector<int>)':
meetings.cpp:48:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < v.size(); i++){
                    ~~^~~~~~~~~~
meetings.cpp:60:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 1; i < path.size(); i++){
                    ~~^~~~~~~~~~~~~
meetings.cpp:63:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < v.size(); i++){
                    ~~^~~~~~~~~~
meetings.cpp: In function 'void Solve(int)':
meetings.cpp:76:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < ans.size(); i++){
                    ~~^~~~~~~~~~~~

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