Submission #611650

#	Time	Username	Problem	Language	Result	Execution time	Memory
611650		alireza_kaviani	Meetings (JOI19_meetings)	C++17	100 / 100	940 ms	848 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;

#define all(x)  (x).begin(), (x).end()
#define SZ(x)   int((x).size())

const int MAXN = 2010;

int n , cur , sz[MAXN] , mx[MAXN] , par[MAXN] , mark[MAXN];
vector<int> adj[MAXN];

int cmp(int x , int y){
    return sz[x] > sz[y];
}

int LCA(int v , int u){
    return Query(0 , v , u);
}

void PreDFS(int v){
    sz[v] = 1; mx[v] = v;
    for(int u : adj[v]){
        PreDFS(u);
        par[u] = v;
        sz[v] += sz[u];
    }
    sort(all(adj[v]) , cmp);
    if(SZ(adj[v]) > 0){
        mx[v] = mx[adj[v][0]];
    }
}

void Insert(int v , int u , int x){
    vector<int> vec;
    while(v != u){
        vec.push_back(v);
        v = par[v];
    }
    vec.push_back(u);
    int l = 0 , r = SZ(vec) - 1;
    while(r - l > 1){
        int mid = l + r >> 1;
        if(LCA(x , vec[mid]) == vec[mid])   r = mid;
        else    l = mid;
    }
    v = vec[r]; u = vec[l];
    adj[v].erase(find(all(adj[v]) , u));
    adj[v].push_back(x);
    adj[x].push_back(u);
    mark[x] = 1;
}

int Solve(int v , int ptr){
    for(int i = ptr ; i < SZ(adj[v]) ; i++){
        int u = adj[v][i];
        int lca = LCA(cur , mx[u]);
        if(lca == v){
            continue;
        }
        if(mark[lca]){
            return Solve(lca , 1);
        }
        Insert(mx[u] , v , lca);
        return lca;
    }
    return v;
}

void Solve(int N) {
    n = N;
    mark[0] = 1;
    for(int i = 1 ; i < n ; i++){
        if(mark[i]) continue;
        PreDFS(0);
        cur = i;
        int p = Solve(0 , 0);
        if(p == i)  continue;
        adj[p].push_back(i);
        mark[i] = 1;
    }
    for(int i = 0 ; i < n ; i++){
        for(int j : adj[i]){
            Bridge(min(i , j) , max(i , j));
        }
    }
}

Compilation message (stderr)

meetings.cpp: In function 'void Insert(int, int, int)':
meetings.cpp:43:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |         int mid = l + r >> 1;
      |                   ~~^~~

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