Submission #650660

#	Time	Username	Problem	Language	Result	Execution time	Memory
650660		OttoTheDino	Meetings (JOI19_meetings)	C++17	100 / 100	1076 ms	1072 KiB

meetings

    #include "meetings.h"
     
    #include <bits/stdc++.h>
    using namespace std;
     
    #define rep(i,s,e)                          for (int i = s; i <= e; ++i)
    #define fi                                  first
    #define se                                  second
    #define all(a)                              a.begin(), a.end()
    #define len(a)                              (int)a.size()
    #define pb                                  push_back
    typedef pair<int,int> ii;
    typedef vector<int> vi;
    typedef vector<ii> vii;
     
    const int mx = 2000;
    vi kids[mx];
    int sz[mx], par[mx], done[mx];
     
    int bot (int u, int id) {
        vii ord;
        for (int v : kids[u]) ord.pb({sz[v],v});
        stable_sort(all(ord));
        reverse(all(ord));
        if (id >= len(ord)) return u;
        return bot (ord[id].se, 0);
    }
     
    void upd (int u) {
        sz[u]++;
        if (par[u]) upd(par[u]);
    }
     
    void Solve(int n) {
     
        done[0] = 1;
     
        rep (i,1,n-1) {
     
            if (done[i]) continue;
     
            int cur = 0, id = 0, y = i, x = -1;
     
            while (true) {
                x = bot(cur, id);
     
                if (x==cur) break;
     
                int res = Query (0, i, x); 
     
                if (!done[res]) {
                    if (res!=i) { 
                        par[i] = res;
                        kids[res].pb(i);
                        y = res;
                    }
                    break;
                }
                
                if (res!=cur) {
                    cur = res;
                    id = 0;
                }
     
                else id++;
            }
            vi a;
            while (x!=0) {
                a.pb(x);
                x = par[x];
            }
            a.pb(0);
     
     
            int lo = 0, hi = len(a)-1;
            while (lo<hi) {
                int mid = (lo+hi)/2;
     
                int res = Query (0, a[mid], y);
     
                if (res==y) lo = mid+1;
                else hi = mid;
            }
     
            par[y] = a[lo];
            kids[a[lo]].pb(y);
     
            if (lo != 0) {
                par[a[lo-1]] = y;
                kids[a[lo]].erase(find(all(kids[a[lo]]),a[lo-1]));
                kids[y].pb(a[lo-1]);
           }
     
            upd(i);
            if (y!=i) upd (y);
            done[i] = done[y] = 1;
        }
     
        rep (i,1,n-1) Bridge(min(par[i],i), max(i,par[i]));
    }

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