Submission #233168

#	Time	Username	Problem	Language	Result	Execution time	Memory
233168		Andrei_Cotor	Meetings (JOI19_meetings)	C++14	100 / 100	1325 ms	3064 KiB

meetings

#include"meetings.h"
#include<random>
#include<algorithm>
#include<chrono>
#include<map>

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<int> Subarb[36005];
vector<int> Path[36005];
int nrs;
map<int,int> IndSub[2005];
int rt;

bool cmp(int a, int b)
{
    if(a==rt)
        return 1;
    if(b==rt)
        return 0;
    int lca=Query(rt,a,b);
    return lca==a;
}

void getArb(int root, int subarb)
{
    shuffle(Subarb[subarb].begin(),Subarb[subarb].end(),rng);
    int nodeOnPath=Subarb[subarb][0];
    if(nodeOnPath==root)
        nodeOnPath=Subarb[subarb][1];

    Path[subarb].clear();
    for(auto node:Subarb[subarb])
    {
        if(node==nodeOnPath || node==root)
            continue;

        int lca=Query(root,node,nodeOnPath);
        if(lca==node)
        {
            Path[subarb].push_back(node);
        }
        else
        {
            if(IndSub[subarb][lca]==0)
            {
                IndSub[subarb][lca]=++nrs;
            }

            Subarb[IndSub[subarb][lca]].push_back(node);
        }
    }

    rt=root;
    Path[subarb].push_back(root);
    Path[subarb].push_back(nodeOnPath);
    sort(Path[subarb].begin(),Path[subarb].end(),cmp);

    for(int i=0; i<Path[subarb].size(); i++)
    {
        if(i<=Path[subarb].size()-2)
        {
            int x=Path[subarb][i];
            int y=Path[subarb][i+1];
            if(x>y)
                swap(x,y);

            Bridge(x,y);
        }

        if(IndSub[subarb][Path[subarb][i]]!=0)
        {
            Subarb[IndSub[subarb][Path[subarb][i]]].push_back(Path[subarb][i]);
            getArb(Path[subarb][i],IndSub[subarb][Path[subarb][i]]);
        }
    }
}

void Solve(int n) 
{
    for(int i=0; i<n; i++)
        Subarb[0].push_back(i);

    getArb(0,0);
}

Compilation message (stderr)

meetings.cpp: In function 'void getArb(int, int)':
meetings.cpp:60:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<Path[subarb].size(); i++)
                  ~^~~~~~~~~~~~~~~~~~~~
meetings.cpp:62:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(i<=Path[subarb].size()-2)
            ~^~~~~~~~~~~~~~~~~~~~~~~

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