Submission #233167

#	Time	Username	Problem	Language	Result	Execution time	Memory
233167		Andrei_Cotor	Meetings (JOI19_meetings)	C++14	0 / 100	120 ms	2376 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)
        {
            Bridge(Path[subarb][i],Path[subarb][i+1]);
        }

        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: 0 / 7
• Subtask 2: 0 / 10
• Subtask 3: 0 / 12
• Subtask 4: 0 / 71