Submission #247700

#	Time	Username	Problem	Language	Result	Execution time	Memory
247700		tqbfjotld	Meetings (JOI19_meetings)	C++14	100 / 100	897 ms	1272 KiB

meetings

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

set<int> adjl[2005];
int sz[2005];
bool block[2005];
bool done[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, int total){
    for (int x : adjl[node]){
        if (x==p) continue;
        if (block[x]) continue;
        if (sz[x]>total/2){
            return findCentroid(x,node,total);
        }
    }
    return node;
}

void addNode(int node, int root){
    dfs(root,-1);
    if (sz[root]==1){
        adjl[root].insert(node);
        adjl[node].insert(root);
        return;
    }
    if (sz[root]==2){
        int ch = -1;
        for (int x : adjl[root]){
            if (block[x]) continue;
            ch = x;
        }
        int res = Query(root,ch,node);
        if (res==root){
            adjl[root].insert(node);
            adjl[node].insert(root);
        }
        else if (res==ch){
            adjl[ch].insert(node);
            adjl[node].insert(ch);
        }
        else if (res==node){
            adjl[root].erase(ch);
            adjl[ch].erase(root);
            adjl[root].insert(node);
            adjl[node].insert(root);
            adjl[ch].insert(node);
            adjl[node].insert(ch);
        }
        else{
            adjl[root].erase(ch);
            adjl[ch].erase(root);
            adjl[root].insert(res);
            adjl[res].insert(root);
            adjl[ch].insert(res);
            adjl[res].insert(ch);
            adjl[res].insert(node);
            adjl[node].insert(res);
            done[res] = true;
        }
        return;
    }
    root = findCentroid(root,-1,sz[root]);
    dfs(root,-1); ///re-root at centroid
    //printf("centroid %d\n",root);
    vector<pair<int,int> > children;
    for (int child : adjl[root]){
        if (block[child]) continue;
        children.push_back({sz[child],child});
        //printf("added %d %d\n",sz[child],child);
    }
    sort(children.begin(),children.end(),greater<pair<int,int> >());
    //assert(children.size()!=1);
    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);
                if (res!=node){
                adjl[res].insert(node);
                adjl[node].insert(res);
                }
            }
            else if (res2==root){
                adjl[root].erase(n2);
                adjl[n2].erase(root);
                adjl[root].insert(res);
                adjl[n2].insert(res);
                adjl[res].insert(root);
                adjl[res].insert(n2);
                if (res!=node){
                adjl[node].insert(res);
                adjl[res].insert(node);
                }
            }
            else{
                //assert(false);
            }
            done[res] = true;
            return;
        }

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

}

void Solve(int N) {
    n = N;
    for (int nw = 1; nw<N; nw++){
        if (done[nw]) continue;
        addNode(nw,0);
        /*for (int x = 0; x<N; x++){
            for (int node : adjl[x]){
                if (node<=x){
                    //printf("now %d, %d--%d\n",nw,node,x);
                }
            }
        }*/
    }
    for (int x = 0; x<N; x++){
        for (int node : adjl[x]){
            if (node<x){
                Bridge(node,x);
            }
        }
    }
}

Compilation message (stderr)

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

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