Submission #205269

#	Time	Username	Problem	Language	Result	Execution time	Memory
205269		egekabas	Meetings (JOI19_meetings)	C++14	29 / 100	3089 ms	3576 KiB

meetings

#include <bits/stdc++.h>
#include "meetings.h"
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long   ll;
typedef unsigned long long   ull;
typedef long double ld;
typedef pair<ll, ll>    pll;
typedef pair<ull, ull>    pull;
typedef pair<int, int>  pii;
typedef pair<ld, ld>  pld;
int p[2009];
vector<int> sub[2009];
int done[2009];
vector<int> cur;
int prt[2009];

void dfs(int v){
    done[v] = 1;
    for(auto u : sub[v])
        if(done[u] == 0)
            dfs(u);
    cur.pb(v);
}
void calc(vector<int> all){
    if(all.size() <= 1) return;
    vector<vector<int>> groups;
    int root = all.back();
    done[root] = 1;
    for(auto u : all){
        if(done[u]) continue;
        for(auto &v : groups){
            int tmp = Query(root, v.back(), u);
            if(tmp == root)
                continue;
            if(u != tmp)
                sub[tmp].pb(u);
            if(v.back() != tmp)
                sub[tmp].pb(v.back());
            cur.clear();
            dfs(tmp);
            v.insert(v.end(), cur.begin(), cur.end());
            break;
        }
        if(done[u] == 0){
            cur.clear();
            dfs(u);
            groups.pb(cur);
        }
    }
    for(auto u : all) done[u] = 0;
    for(auto v : groups){
        p[v.back()] = root;
        calc(v);
    }
}
    
void Solve(int n){
    vector<int> all;
    for(int i = n-1; i >= 0; --i)
        all.pb(i);
    calc(all);
    for(int i = 1; i < n; ++i){
        //cout << i << ' ' << p[i] << '\n';
        Bridge(min(i, p[i]), max(i, p[i]));
    }
}

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