Submission #1287868

#	Time	Username	Problem	Language	Result	Execution time	Memory
1287868		simona1230	Meetings (JOI19_meetings)	C++20	29 / 100	531 ms	10212 KiB

meetings

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

set<int> s[200001];
int use[200001],done[200001];
void Solve(int n)
{
    s[0].insert(1);
    s[1].insert(0);

    for(int i=2; i<n; i++)
    {
        if(done[i])continue;
        for(int j=0;j<n;j++)
            use[j]=0;
        int a=0,c=*s[0].begin();
        bool f=0;

        while(!f)
        {
            int q=Query(a,i,c);
            //cout<<"! "<<a<<" "<<i<<" "<<c<<" "<<q<<endl;
            use[a]=use[c]=1;
            if(q==i)
            {
                f=1;
                s[a].erase(c);
                s[c].erase(a);

                s[a].insert(i);
                s[c].insert(i);

                s[i].insert(a);
                s[i].insert(c);
            }
            else if(q!=a&&q!=c)
            {
                f=1;
                s[a].erase(c);
                s[c].erase(a);

                s[a].insert(q);
                s[c].insert(q);
                s[i].insert(q);

                s[q].insert(a);
                s[q].insert(c);
                s[q].insert(i);
                done[q]=1;
            }
            else
            {
                if(c==q)swap(a,c);

                int nb=-1;
                for(auto it=s[a].begin(); it!=s[a].end(); it++)
                {
                    if(!use[*it])
                    {
                        nb=*it;
                        break;
                    }
                }

                if(nb==-1)
                {
                    f=1;
                    s[a].insert(i);
                    s[i].insert(a);
                }
                else
                {
                    c=nb;
                }
            }
        }
    }

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

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