Submission #1236512

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236512		vivkostov	Meetings (JOI19_meetings)	C++20	100 / 100	887 ms	868 KiB

meetings

//#pragma once
//#include "grader.cpp"
#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
int n,br,root,cen,used[2005],dp[2005],ind1,ind2,added[2005];
vector<int>v[2005];
void push_between(int a,int b,int st)
{
    v[st].push_back(a);
    v[st].push_back(b);
    //cout<<a<<" "<<b<<" "<<st<<endl;
    for(int i=0;i<v[a].size();i++)
    {
        if(v[a][i]==b)
        {
            //cout<<v[a][i]<<endl;
            v[a][i]=st;
            break;
        }
    }
    for(int i=0;i<v[b].size();i++)
    {
        if(v[b][i]==a)
        {
            //cout<<v[b][i]<<endl;
            v[b][i]=st;
            break;
        }
    }
}
void make_dp(int beg)
{
    int w;
    dp[beg]=1;
    used[beg]=5;
    for(int i=0;i<v[beg].size();i++)
    {
        w=v[beg][i];
        if(!used[w])
        {
            make_dp(w);
            dp[beg]+=dp[w];
        }
    }
}
void find_centroid(int beg,int par,int num)
{
    int w;
    for(int i=0;i<v[beg].size();i++)
    {
        w=v[beg][i];
        if(used[w]==1||w==par)continue;
        if(dp[w]>=(num+1)/2)
        {
            find_centroid(w,beg,num);
            return;
        }
    }
    cen=beg;
}
void clea(int beg,int par)
{
    int w;
    dp[beg]=0;
    used[beg]=0;
    for(int i=0;i<v[beg].size();i++)
    {
        w=v[beg][i];
        if(used[w]!=5||w==par)continue;
        clea(w,beg);
    }
}
void make_sz()
{
    clea(root,0);
    used[cen]=5;
    int ma1=0,ma2=0,w;
    ind1=-1;
    ind2=-1;
    for(int i=0;i<v[cen].size();i++)
    {
        w=v[cen][i];
        if(used[w]==1)continue;
        make_dp(w);
        if(ma1<dp[w])
        {
            ma2=ma1;
            ind2=ind1;
            ma1=dp[w];
            ind1=w;
        }
        else if(ma2<dp[w])
        {
            ma2=dp[w];
            ind2=w;
        }
    }
    used[cen]=0;
}
void mix(int ind,int st)
{
    int q=Query(min(cen,ind),max(cen,ind),st);
    if(q==ind)
    {
        v[ind].push_back(st);
        v[st].push_back(ind);
        br++;
    }
    else if(q==cen)
    {
        v[cen].push_back(st);
        v[st].push_back(cen);
        br++;
    }
    else if(q==st)
    {
        push_between(ind,cen,st);
        br++;
    }
    else
    {
        push_between(ind,cen,q);
        added[q]=1;
        v[q].push_back(st);
        v[st].push_back(q);
        br+=2;
    }
}
void add(int st)
{
    root=0;
    cen=0;
    memset(dp,0,sizeof(dp));
    memset(used,0,sizeof(used));
    int num=0,flag=0;
    /*cout<<st<<endl;
    for(int i=0;i<n;i++)
    {
        cout<<i<<" : ";
        for(int j=0;j<v[i].size();j++)
        {
            cout<<v[i][j]<<" ";
        }
        cout<<endl;
    }*/
    while(true)
    {
        make_dp(root);
        num=dp[root];
        find_centroid(root,root,num);
        make_sz();
        //cout<<ind1<<" "<<ind2<<" "<<cen<<" "<<num<<" "<<root<<endl;
        if(ind1==-1)
        {
            v[cen].push_back(st);
            v[st].push_back(cen);
            br++;
            break;
        }
        if(ind2==-1)
        {
            mix(ind1,st);
            break;
        }
        if(num==3)
        {
            int q=Query(min(cen,ind2),max(cen,ind2),st);
            if(q==ind2)
            {
                v[ind2].push_back(st);
                v[st].push_back(ind2);
                br++;
                break;
            }
            if(q==st)
            {
                push_between(ind2,cen,st);
                br++;
                break;
            }
            if(q!=cen)
            {
                push_between(ind2,cen,q);
                v[q].push_back(st);
                v[st].push_back(q);
                added[q]=1;
                br+=2;
                break;
            }
            mix(ind1,st);
            break;
        }
        int q=Query(ind1,ind2,st);
        if(q!=cen&&q!=ind1&&q!=ind2)
        {
            for(int i=0;i<n;i++)
            {
                used[i]=1;
            }
            root=cen;
            used[cen]=0;
            used[ind1]=0;
            used[ind2]=0;
            continue;
        }
        clea(cen,cen);
        root=q;
        if(q==cen)
        {
            used[ind1]=1;
            used[ind2]=1;
        }
        else
        {
            used[cen]=1;
        }
        /*cout<<cen<<" "<<ind1<<" "<<ind2<<endl;
        for(int i=0;i<n;i++)
        {
            cout<<used[i]<<" ";
        }
        cout<<endl;*/
        flag++;
        if(flag==20)break;
    }
}
void Solve(int N)
{
    n=N;
    br=1;
    for(int i=1;i<n;i++)
    {
        if(!added[i])add(i);
    }
    for(int i=0;i<n;i++)
    {
        //cout<<i<<" : ";
        for(int j=0;j<v[i].size();j++)
        {
            //cout<<v[i][j]<<" ";
            if(v[i][j]>i)Bridge(i,v[i][j]);
        }
        //cout<<endl;
    }
}

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