Submission #208747

#	Time	Username	Problem	Language	Result	Execution time	Memory
208747		erd1	Meetings (JOI19_meetings)	C++14	29 / 100	2296 ms	1144 KiB

meetings

#include<utility>
#include<vector>
#include<algorithm>
#include<numeric>
#include<queue>
#include<iostream>
#include<unordered_map>
#include<unordered_map>

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);
void bridge(int i, int j){
    //cout << i << " " << j << endl;
    Bridge(min(i, j), max(i, j));
}

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;
    unordered_map<int, vector<int>> m; vector<int> ch;
    m[r], m[v[0]];
    for(int cur = v[0], i = 1; i < v.size(); i++){
        int x = Query(r, cur, v[i]);
        if(x == cur)m[cur = v[i]];
        else if(x == v[i])m[x];
        else m[x].pb(v[i]);
    }
    for(auto& i: m){
        if(i.ss.size())solve(r = i.ff, i.ss);
        ch.pb(i.ff);
    }
    sort(all(ch), [](int a, int b) {
        if(!a)return true; if(!b)return false;
        return a != b && Query(0, a, b) == a;
    });
    for(int i = 1; i < ch.size(); i++)bridge(ch[i-1], ch[i]);
}

void Solve(int N){
    vector<int> v(N-1);
    iota(all(v), 1);
    solve(0, v);
}

Compilation message (stderr)

meetings.cpp: In function 'void solve(int, std::vector<int>&)':
meetings.cpp:84:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int cur = v[0], i = 1; i < v.size(); i++){
                                ~~^~~~~~~~~~
meetings.cpp: In lambda function:
meetings.cpp:95:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
         if(!a)return true; if(!b)return false;
         ^~
meetings.cpp:95:28: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
         if(!a)return true; if(!b)return false;
                            ^~
meetings.cpp: In function 'void solve(int, std::vector<int>&)':
meetings.cpp:98:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 1; i < ch.size(); i++)bridge(ch[i-1], ch[i]);
                    ~~^~~~~~~~~~~

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