제출 #1291266

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1291266		simona1230	Meetings (JOI19_meetings)	C++20	0 / 100	247 ms	10160 KiB

meetings

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

set<int> s[200001];
int sz[200001],d[200001];
int n;

void dfs(int i,int p)
{
    //cout<<i<<" ";
    sz[i]=1;
    for(auto it=s[i].begin(); it!=s[i].end(); it++)
    {
        int nb=*it;
        if(nb==p||d[nb])continue;

        dfs(nb,i);
        sz[i]+=sz[nb];
    }
}

int all;
int cent(int i,int p)
{
    for(auto it=s[i].begin(); it!=s[i].end(); it++)
    {
        int nb=*it;
        if(nb==p||d[nb])continue;

        if(sz[nb]>all/2)return cent(nb,i);
    }

    return i;
}

set<int> ver;
int curr;

void hey(int x)
{
    //cout<<x<<" innnn "<<endl;
    dfs(x,-1);
    //cout<<endl;
    all=sz[x];

    if(all==1)
    {
        s[x].insert(curr);
        s[curr].insert(x);
        return;
    }

    int c=cent(x,-1);
    //cout<<c<<endl;
    d[c]=1;

    vector<int> nb;
    for(auto it=s[c].begin(); it!=s[c].end(); it++)
        if(!d[*it])nb.push_back(*it);

    for(int i=1; i<nb.size(); i+=2)
    {
        int nb1=nb[i-1];
        int nb2=nb[i];

        int y=Query(nb1,nb2,curr);
        if(y==nb1)
        {
            hey(nb1);
            return;
        }

        if(y==nb2)
        {
            hey(nb2);
            return;
        }

        if(y==curr)
        {
            int yy=Query(nb1,c,curr);
            if(yy==curr)
            {
                s[nb1].erase(c);
                s[c].erase(nb1);
                s[curr].insert(nb1);
                s[nb1].insert(curr);
                s[curr].insert(c);
                s[c].insert(curr);
                return;
            }
            else
            {
                s[nb2].erase(c);
                s[c].erase(nb2);
                s[curr].insert(nb2);
                s[nb2].insert(curr);
                s[curr].insert(c);
                s[c].insert(curr);
                return;
            }
        }

        if(y!=c)
        {
            int yy=Query(nb1,c,curr);
            s[curr].insert(y);
            s[y].insert(curr);
            ver.erase(y);
            if(yy==y)
            {
                s[nb1].erase(c);
                s[c].erase(nb1);
                s[y].insert(nb1);
                s[nb1].insert(y);
                s[y].insert(c);
                s[c].insert(y);
                return;
            }
            else
            {
                s[nb2].erase(c);
                s[c].erase(nb2);
                s[y].insert(nb2);
                s[nb2].insert(y);
                s[y].insert(c);
                s[c].insert(y);
                return;
            }
        }
    }

    if(nb.size()%2==1)
    {
        int nb1=nb[nb.size()-1];
        int y=Query(nb1,c,curr);
        //cout<<"here "<<y<<" "<<nb1<<endl;
        if(y==c)
        {
            s[c].insert(curr);
            s[curr].insert(c);
            return;
        }

        if(y==nb1)
        {
            hey(nb1);
            return;
        }

        if(curr!=y)
        {
            s[curr].insert(y);
            s[y].insert(curr);
            ver.erase(y);
        }

        s[nb1].erase(c);
        s[c].erase(nb1);
        s[y].insert(nb1);
        s[nb1].insert(y);
        s[y].insert(c);
        s[c].insert(y);
    }
}

void Solve(int N)
{
    n=N;
    for(int i=1; i<n; i++)
        ver.insert(i);

    while(ver.size())
    {
        for(int i=0; i<n; i++)
            d[i]=0;
        curr=*ver.begin();
        ver.erase(curr);

        hey(0);
        //cout<<"!!!!!! "<<curr<<endl;

    }

    for(int i=0; i<n; i++)
    {
        for(auto it=s[i].begin(); it!=s[i].end(); it++)
        {
            int nb=*it;
            //cout<<i<<" - "<<nb<<endl;
            if(i<nb)Bridge(i,nb);
        }
    }
}

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