Submission #674076

#	Time	Username	Problem	Language	Result	Execution time	Memory
674076		lukameladze	Meetings (JOI19_meetings)	C++14	100 / 100	426 ms	1980 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define pii pair <int, int>
#define pb push_back

const int NN = 3005;
vector <int> g[NN];
int n;

vector <int> merge_sort(vector <int > ve, int x) {
    if (ve.size() <= 1) return ve;
    int mid = ((int)ve.size() - 1) / 2;
    vector <int> vle, vri;
    for (int i = 0; i <= mid; i++) {
        vle.pb(ve[i]);
    }
    for (int i = mid + 1; i < ve.size(); i++) {
        vri.pb(ve[i]);
    }
    
    vle = merge_sort(vle, x);
    vri = merge_sort(vri, x);
    int curl = 0, szl = vle.size(); int curr = 0, szr = vri.size();
    vector <int> ans;
    while (curl < szl || curr < szr) {
        if (curl == szl) {
            ans.pb(vri[curr]); curr++; continue;
        }
        if (curr == szr) {
            ans.pb(vle[curl]); curl++; continue;
        }
        int result = Query(x,vle[curl],vri[curr]);
        if (vle[curl] == result) {
            ans.pb(vle[curl]); curl++;
        } else ans.pb(vri[curr]), curr++;
    }
	vle.clear(); vri.clear();
    return ans;
}
void go(vector <int> v) {
    random_shuffle(v.begin(),v.end());
    vector <int> sub[n + 5];
    for (int i = 0; i < v.size(); i++) sub[v[i]].clear();
    if (v.size() <= 1) return ;
    if (v.size() == 2) {
        g[min(v[0],v[1])].pb(max(v[0],v[1]));
        return ;
    }
    int x = v[0]; int y = v[1];
    sub[x].pb(x);
    sub[y].pb(y);

    vector <int> ve;
    for (int i = 0; i < v.size(); i++) {
        if (v[i] == x || v[i] == y) continue;
        int result = Query(x,y,v[i]);
        if (sub[result].size() == 0) ve.pb(result); 
        sub[result].pb(v[i]);
    }
    vector <int> res = merge_sort(ve,x);
    vector <int> pv;
    pv.pb(x); for (int x : res) pv.pb(x); pv.pb(y);
    
    for (int i = 0; i < pv.size(); i++) {
        if (i >= 1) g[min(pv[i - 1], pv[i])].pb(max(pv[i - 1], pv[i]));
        go(sub[pv[i]]);
    }
    
}
void Solve(int N) {
  n = N;
  vector <int> v;
  for (int i = 0; i < n; i++) {
      v.pb(i);
  }
  go(v);
  for (int i = 0; i < n; i++) {
      for (int to : g[i]) Bridge(i, to);
  }
}

Compilation message (stderr)

meetings.cpp: In function 'std::vector<int> merge_sort(std::vector<int>, int)':
meetings.cpp:20:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for (int i = mid + 1; i < ve.size(); i++) {
      |                           ~~^~~~~~~~~~~
meetings.cpp: In function 'void go(std::vector<int>)':
meetings.cpp:46:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     for (int i = 0; i < v.size(); i++) sub[v[i]].clear();
      |                     ~~^~~~~~~~~~
meetings.cpp:57:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     for (int i = 0; i < v.size(); i++) {
      |                     ~~^~~~~~~~~~
meetings.cpp:67:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |     for (int i = 0; i < pv.size(); i++) {
      |                     ~~^~~~~~~~~~~

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