oj.uz

답안 #247695

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
247695 2020-07-12T00:43:22 Z tqbfjotld Meetings (JOI19_meetings) C++14
0 / 100
 2 ms 640 KB 
#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;

set<int> adjl[2005];
int sz[2005];
bool block[2005];
int n;

void dfs(int node, int p){
    sz[node] = 1;
    for (int x : adjl[node]){
        if (x==p) continue;
        if (block[x]) continue;
        dfs(x,node);
        sz[node] += sz[x];
    }
}

int findCentroid(int node, int p){
    for (int x : adjl[node]){
        if (x==p) continue;
        if (block[x]) continue;
        if (sz[x]>n/2){
            return findCentroid(x,node);
        }
    }
    return node;
}

void addNode(int node, int root){
    dfs(root,-1);
    if (sz[root]==1){
        adjl[root].insert(node);
        adjl[node].insert(root);
        return;
    }
    root = findCentroid(root,-1);
    dfs(root,-1); ///re-root at centroid
    vector<pair<int,int> > children;
    for (int child : adjl[root]){
        children.push_back({sz[child],child});
    }
    sort(children.begin(),children.end(),greater<pair<int,int> >());
    if (children.size()&1){
        children.push_back(children[0]);
    }
    for (int x = 0; x<children.size(); x+=2){
        int n1 = children[x].second;
        int n2 = children[x+1].second;
        int res = Query(node,n1,n2);
        if (res==n1){
            block[root] = true;
            addNode(node,n1);
            block[root] = false;
            return;
        }
        if (res==n2){
            block[root] = true;
            addNode(node,n2);
            block[root] = false;
            return;
        }
        if (res!=root){
            ///res is either on edge root-n1 or root-n2
            int res2 = Query(root,n1,res);
            if (res2==res){
                adjl[root].erase(n1);
                adjl[n1].erase(root);
                adjl[root].insert(res);
                adjl[n1].insert(res);
                adjl[res].insert(root);
                adjl[res].insert(n1);
            }
            else{
                adjl[root].erase(n2);
                adjl[n2].erase(root);
                adjl[root].insert(res);
                adjl[n2].insert(res);
                adjl[res].insert(root);
                adjl[res].insert(n2);
            }
            return;
        }

    }
    ///directly connected to root
    adjl[root].insert(node);
    adjl[node].insert(root);

}

void Solve(int N) {
    n = N;
    int x = Query(0, 1, 2);
    for (int i = 0; i<3; i++){
        if (i!=x){
            adjl[i].insert(x);
            adjl[x].insert(i);
        }
    }
    for (int nw = 3; nw<N; nw++){
        addNode(nw,0);
    }
    for (int x = 0; x<N; x++){
        for (int node : adjl[x]){
            if (node<x){
                Bridge(node,x);
            }
        }
    }
}

Compilation message

meetings.cpp: In function 'void addNode(int, int)':
meetings.cpp:48:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int x = 0; x<children.size(); x+=2){
                     ~^~~~~~~~~~~~~~~~

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 544 KB Output is correct
2 Incorrect 0 ms 512 KB Wrong Answer [1]
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 544 KB Output is correct
2 Incorrect 0 ms 512 KB Wrong Answer [1]
3 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 544 KB Output is correct
2 Incorrect 0 ms 512 KB Wrong Answer [1]
3 Halted 0 ms 0 KB -

Subtask #4
0 / 71.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 640 KB Wrong Answer [1]
2 Halted 0 ms 0 KB -