oj.uz

Submission #611628

# Submission time Handle Problem Language Result Execution time Memory
611628 2022-07-29T06:08:21 Z alireza_kaviani Meetings (JOI19_meetings) C++17
0 / 100
 149 ms 262144 KB 
#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);
        adj[p].push_back(i);
        mark[cur] = 1;
    }
    for(int i = 0 ; i < n ; i++){
        for(int j : adj[i]){
            Bridge(i , j);
        }
    }
}

Compilation message

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
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 336 KB Output is correct
2 Runtime error 149 ms 262144 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 336 KB Output is correct
2 Runtime error 149 ms 262144 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 336 KB Output is correct
2 Runtime error 149 ms 262144 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #4
0 / 71.0

# Verdict Execution time Memory Grader output
1 Runtime error 145 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -