oj.uz

Submission #123706

# Submission time Handle Problem Language Result Execution time Memory
123706 2019-07-02T05:08:59 Z 박상수(#3035) Meetings (JOI19_meetings) C++14
0 / 100
 843 ms 776 KB 
#include "meetings.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_set>
#include <bitset>
#include <time.h>
#include <limits.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define Fi first
#define Se second
#define pb push_back
#define szz(x) (int)x.size()
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) x.begin(),x.end()
typedef tuple<int, int, int> t3;

vector <pii> ans;
vector <int> E[2020];
int chk[2020], rt, down[2020], pp[2020];
int mark[2020];

void add_edge(int x, int y) { E[x].pb(y); E[y].pb(x); }
void del_edge(int x, int y) {
    rep(i, szz(E[x])) if(E[x][i] == y) { swap(E[x][i], E[x].back()); E[x].pop_back(); break; }
    rep(i, szz(E[y])) if(E[y][i] == x) { swap(E[y][i], E[y].back()); E[y].pop_back(); break; }
}

int Temp[2020], tp;
void pdfs(int x, int fa = -1) {
    Temp[tp++] = x;
    down[x] = 1;
    for(int e : E[x]) if(e != fa && mark[e] == 0) {
        pp[e] = x;
        pdfs(e, x);
        down[x] += down[e];
    }
}

void solve(int rt, int x) {
    if(chk[x]) return;
    tp = 0; pdfs(rt);
    int f1 = -1, f2 = -1, cnt = down[rt], fv = -1;
    if(cnt == 1) {
        add_edge(rt, x);
        return;
    }
    rep(a, tp) if(Temp[a] != rt) {
        int i = Temp[a];
        if(min(down[i], cnt-down[i]) > fv) {
            fv = min(down[i], cnt-down[i]);
            f1 = i, f2 = pp[i];
        }
    }
    int v = Query(f1, f2, x);
    if(v != f1 && v != f2) {
        del_edge(f1, f2);
        add_edge(f1, v);
        add_edge(f2, v);
        if(x != v) add_edge(x, v);
        chk[x] = chk[v] = 1;
        return;
    }
    if(v == f1) {
        mark[f2] = 1;
        solve(f1, x);
    }
    else {
        mark[f1] = 1;
        solve(f2, x);
    }
}

void Solve(int N) {
    vector <int> X; rep(i, N) X.pb(i);
    random_shuffle(all(X));
    chk[rt=X[0]] = 1;
    add_edge(X[0], X[1]);
    
    for(int i=2;i<N;i++) { memset(mark, 0, sizeof mark); solve(X[0], X[i]); }
    rep(i, N) for(int e : E[i]) if(i < e) Bridge(i, e), printf("%d %d\n", i, e);
    
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 504 KB DO NOT PRINT ANYTHING TO STANDARD OUTPUT
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 504 KB DO NOT PRINT ANYTHING TO STANDARD OUTPUT
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 504 KB DO NOT PRINT ANYTHING TO STANDARD OUTPUT
2 Halted 0 ms 0 KB -

Subtask #4
0 / 71.0

# Verdict Execution time Memory Grader output
1 Incorrect 843 ms 776 KB DO NOT PRINT ANYTHING TO STANDARD OUTPUT
2 Halted 0 ms 0 KB -