Submission #198926

#	Time	Username	Problem	Language	Result	Execution time	Memory
198926		L01	Split the Attractions (IOI19_split)	C++17	18 / 100	155 ms	10744 KiB

split

#include "split.h"
#include<bits/stdc++.h>
using namespace std;
int extremo1,extremo2,numvis;
vector<int>vis,siguiente[100005];
queue<int>cola;
int encuentraextremo(int origen,int color)
{
    int distancia[100005],ultimo;
    numvis=color;
    cola.push(origen);
    distancia[origen]=0;
    vis[origen]=numvis;
    while(!cola.empty())
    {
        int actual=cola.front();
        cola.pop();
        for(int i=0;i<siguiente[actual].size();i++)
        {
            int nuevo=siguiente[actual][i];
            if(vis[nuevo]!=numvis)
            {
                vis[nuevo]=numvis;
                distancia[nuevo]=distancia[actual]+1;
                cola.push(nuevo);
            }
        }
        ultimo=actual;
    }
    return ultimo;
}
int visita(int telementos,int origen,int grupo)
{
    int tvisitados=0;
    numvis=grupo;
    cola.push(origen);
    while((!cola.empty()) and tvisitados<telementos)
    {
        int actual=cola.front();
        cola.pop();
        if(vis[actual]>3)
        {
            vis[actual]=numvis;
            tvisitados++;
            for(int i=0;i<siguiente[actual].size();i++)
            {
                int nuevo=siguiente[actual][i];
                if(vis[nuevo]!=numvis)
                    cola.push(nuevo);
            }
        }
    }
    while(!cola.empty())
        cola.pop();
    return tvisitados;
}
void rellena(int grupo,int tnumeros)
{
    for(int i=0;i<tnumeros;i++)
    {
        if(vis[i]>3)
            vis[i]=grupo;
    }
}
vector<int> find_split(int tnodos,int telementos1,int telementos2,int telementos3,vector<int> origen,vector<int> destino)
{
	for(int i=0;i<origen.size();i++)
    {
        siguiente[origen[i]].push_back(destino[i]);
        siguiente[destino[i]].push_back(origen[i]);
    }
    vis.resize(tnodos);
    extremo1=encuentraextremo(0,5);
    extremo2=encuentraextremo(extremo1,4);
    if(telementos1<=telementos3 and telementos2<=telementos3)
    {
        visita(telementos1,extremo1,1);
        if(telementos2==visita(telementos2,extremo2,2))
        {
            rellena(3,tnodos);
        }
        else
        {
            vis.resize(0);
            vis.resize(tnodos);
        }
    }
    else
    {
        if(telementos1<=telementos2 and telementos3<=telementos2)
        {
            visita(telementos1,extremo1,1);
            if(telementos3==visita(telementos3,extremo2,3))
            {
                rellena(2,tnodos);
            }
            else
            {
                vis.resize(0);
                vis.resize(tnodos);
            }
        }
        else
        {
            visita(telementos2,extremo1,2);
            if(telementos3==visita(telementos3,extremo2,3))
            {
                rellena(1,tnodos);
            }
            else
            {
                vis.resize(0);
                vis.resize(tnodos);
            }
        }
    }
    return vis;
}

Compilation message (stderr)

split.cpp: In function 'int encuentraextremo(int, int)':
split.cpp:18:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<siguiente[actual].size();i++)
                     ~^~~~~~~~~~~~~~~~~~~~~~~~~
split.cpp: In function 'int visita(int, int, int)':
split.cpp:45:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i=0;i<siguiente[actual].size();i++)
                         ~^~~~~~~~~~~~~~~~~~~~~~~~~
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:67:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<origen.size();i++)
              ~^~~~~~~~~~~~~~
split.cpp: In function 'int encuentraextremo(int, int)':
split.cpp:30:12: warning: 'ultimo' may be used uninitialized in this function [-Wmaybe-uninitialized]
     return ultimo;
            ^~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 0 / 22
• Subtask 4: 0 / 24
• Subtask 5: 0 / 36