Submission #208777

#	Time	Username	Problem	Language	Result	Execution time	Memory
208777		erd1	Meetings (JOI19_meetings)	C++14	100 / 100	1244 ms	1016 KiB

meetings

#include<utility>
#include<vector>
#include<algorithm>
#include<numeric>
#include<queue>
#include<iostream>
#include<map>
#include<set>

using namespace std;
typedef int64_t lld;
typedef pair<int,int> pii;
typedef pair<lld,lld> pll;
typedef pair<int,pll> pip;
typedef pair<pll,int> ppi;
typedef pair<lld,pll> plp;
typedef pair<pll,lld> ppl;
typedef pair<pll,pll> ppp;
template<typename T>
using maxHeap = priority_queue<T,vector<T>,less<T>>;
template<typename T>
using minHeap = priority_queue<T,vector<T>,greater<T>>;
#define ff first
#define ss second
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define endl '\n'
#define jizz cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
inline void input(int &_x) {
    _x = 0;
    int _tmp = 1; char _tc = getchar();
    while((_tc < '0' || _tc > '9') && _tc != '-') _tc = getchar();
    if(_tc == '-') _tc = getchar(), _tmp = -1;
    while(_tc >= '0' && _tc <= '9') _x = _x*10+(_tc-48), _tc = getchar();
    _x *= _tmp;
}
inline void output(int _x) {
    char _buff[20]; int _f = 0;
    if(_x == 0)putchar('0');
    while(_x > 0)
    {
        _buff[_f++] = _x%10+'0';
        _x /= 10;
    }
    for(_f-=1; _f >= 0; _f--)
        putchar(_buff[_f]);
    putchar('\n');
}
template<typename Iter>
ostream& _out(ostream &s, Iter b, Iter e) {
    s<<"[";
    for ( auto it=b; it!=e; it++ ) s<<(it==b?"":" ")<<*it;
    s<<"]";
    return s;
}
template<class T1,class T2>
ostream& operator<<(ostream& out, pair<T1,T2> p) {
    return out << '(' << p.first << ", " << p.second << ')';
}
template<typename T>
ostream& operator <<( ostream &s, const vector<T> &c ) {
     return _out(s,c.begin(),c.end());
 }
#ifdef erd1
    #define pprint(x) cerr<<__PRETTY_FUNCTION__<<":"<<__LINE__<<" - "<<(#x)<<"="<<(x)<<endl
#else
    #define pprint(x)
#endif

// code starts here
int Query(int, int, int);
void Bridge(int, int);

int query(int a, int b, int c){
    static int x = 0;
    if(++x > 40000)exit(0);
    return Query(a, b, c);
}

inline void bridge(int i, int j){
    //cout << i << " " << j << endl;
    Bridge(min(i, j), max(i, j));
}

int curr = 0, biggest = -1;

struct comp {
    bool operator()(int a, int b){
        if(a == b)return false;
        if(a == curr)return true;
        if(b == curr)return false;
        if(a == biggest)return false;
        if(b == biggest)return true;
        return query(curr, a, b) == a;
    }
};
inline void insert(set<int, comp>& s, int a){
    biggest = a, s.insert(a), biggest = -1;
}
void solve(int r, vector<int>& v){
    //cout << r << v << endl;
    if(v.size() == 1) return bridge(r, v[0]);
    if(v.size() <= 1) return;
    curr = r;
    map<int, vector<int>> m; set<int, comp> ch;
    m[r], m[v[0]];
    ch.insert(r); insert(ch, v[0]);
    for(int cur = v[0], i = 1; i < v.size(); i++){
        int x = query(r, cur, v[i]);
        if(x == cur){
            if(m.find(cur) == m.end())
                m[cur], insert(ch, cur);
            cur = v[i];
        } else {
            if(m.find(x) == m.end())
                m[x], ch.insert(x);
            if(x != v[i])
                m[x].pb(v[i]);
        }
        if(i == v.size()-1)
            if(m.find(cur) == m.end())
                m[cur], insert(ch, cur);
    }
    for(auto& i: m)
        if(i.ss.size())solve(r = i.ff, i.ss);
    for(auto it1 = ch.begin(), it2 = next(it1); it2 != ch.end(); it1++, it2++)
        bridge(*it1, *it2);
}

void Solve(int N){
    vector<int> v(N);
    srand((intptr_t)(void*)new int());
    iota(all(v), 0);
    random_shuffle(all(v));
    int x = v.back(); v.pop_back();
    solve(x, v);
}

Compilation message (stderr)

meetings.cpp: In function 'void solve(int, std::vector<int>&)':
meetings.cpp:108:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int cur = v[0], i = 1; i < v.size(); i++){
                                ~~^~~~~~~~~~
meetings.cpp:120:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(i == v.size()-1)
            ~~^~~~~~~~~~~~~

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