Submission #158993

#	Time	Username	Problem	Language	Result	Execution time	Memory
158993		combi1k1	Meetings (JOI19_meetings)	C++14	0 / 100	88 ms	504 KiB

meetings

#include<bits/stdc++.h>
#include "meetings.h"

using namespace std;

#define X   first
#define Y   second

typedef pair<int,int>   ii;

void wtf(int u,int v)   {
    if (u > v)
        swap(u,v);
    Bridge(u,v);
}

void calc(vector<int> Ver,int P)    {
    int n = Ver.size();
    if (n == 1) {
        wtf(Ver[0],P);
        return;
    }

    int x = Ver[rand() % n];

    vector<ii>  Remain;
    vector<int> toRoot(1,x);

    for(int a : Ver)    if (a != x) {
        int u = Query(P,a,x);
        if (u == a)
            toRoot.push_back(u);
        else
            Remain.push_back({u,a});
    }

    sort(Remain.begin(),Remain.end());
    sort(toRoot.begin(),toRoot.end(),[&](int x,int y)   {
        return  Query(P,x,y) == x;
    });
    toRoot.erase(unique(toRoot.begin(),toRoot.end()),toRoot.end());

    for(int x : toRoot)
        wtf(x,P),
        P = x;

    int l = 0;
    int r = 0;
    Ver.clear();

    for(; l < Remain.size() ;)  {
        for(; r < Remain.size() && Remain[r].X == Remain[l].X ; ++r)    Ver.push_back(Remain[r].Y);
        calc(Ver, Remain[l].X);
        l = r;
    }
}

void Solve(int n)   {
    srand(time(NULL));

    vector<int> Ver(n - 1);

    iota(Ver.begin(),Ver.end(),1);
    calc(Ver,0);
}

Compilation message (stderr)

meetings.cpp: In function 'void calc(std::vector<int>, int)':
meetings.cpp:51:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(; l < Remain.size() ;)  {
           ~~^~~~~~~~~~~~~~~
meetings.cpp:52:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(; r < Remain.size() && Remain[r].X == Remain[l].X ; ++r)    Ver.push_back(Remain[r].Y);
               ~~^~~~~~~~~~~~~~~

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