Submission #1235804

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235804		vivkostov	Meetings (JOI19_meetings)	C++20	29 / 100	1279 ms	900 KiB

meetings

//#pragma once
//#include "grader.cpp"
#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
int n,mat[305][305],br,leaf[305],used[305],used2[305],lamp;
map<int,int>m[305];
void prec()
{
    for(int i=1;i<n;i++)
    {
        for(int j=i+1;j<n;j++)
        {
            mat[i][j]=Query(0,i,j);
        }
    }
}
void fix()
{
    for(int i=1;i<n;i++)
    {
        if(leaf[i]==2)
        {
            Bridge(0,i);
        }
    }
    lamp=1;
}
void resh()
{
    int num_leaf=0;
    for(int i=1;i<n;i++)
    {
        if(leaf[i])continue;
        for(int j=i+1;j<n;j++)
        {
            if(leaf[j])continue;
            used[mat[i][j]]++;
        }
    }
    for(int i=1;i<n;i++)
    {
        if(leaf[i])continue;
        if(!used[i])
        {
            num_leaf++;
            leaf[i]=2;
        }
    }
    if(num_leaf+1==br)
    {
        fix();
        return;
    }
    for(int i=1;i<n;i++)
    {
        if(leaf[i]==2)
        {
            for(int j=i+1;j<n;j++)
            {
                if(leaf[j]==2)
                {
                    used2[mat[i][j]]++;
                    m[mat[i][j]][i]=1;
                }
            }
        }
    }
    int sz;
    for(int i=1;i<n;i++)
    {
        if(leaf[i]==1)continue;
        //cout<<used[i]<<" "<<used2[i]<<" "<<m[i].size()<<endl;
        sz=m[i].size();
        if(used[i]==used2[i]+m[i].size()+1)
        {
            //cout<<i<<endl;
            for(auto j=m[i].begin();j!=m[i].end();j++)
            {
                Bridge(min(i,j->first),max(i,j->first));
                leaf[j->first]=1;
                br--;
            }
            for(int j=1;j<n;j++)
            {
                if(leaf[j]==1||j==i)continue;
                if(mat[min(i,j)][max(i,j)]==i)
                {
                    //cout<<i<<" "<<j<<endl;
                    Bridge(min(i,j),max(i,j));
                    leaf[j]=1;
                    br--;
                }
            }
        }
    }
    for(int i=1;i<n;i++)
    {
        m[i].clear();
        if(leaf[i]==2)leaf[i]=0;
    }
    memset(used,0,sizeof(used));
    memset(used2,0,sizeof(used2));
}
void Solve(int N)
{
    n=N;
    br=n;
    prec();
    int b=0;
    //cout<<endl;
    while(!lamp)
    {
        resh();
        //b++;
        //cout<<br<<endl;
        //if(b==1)return;
    }
}

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