Submission #198926

# Submission time Handle Problem Language Result Execution time Memory
198926 2020-01-28T07:18:55 Z L01 Split the Attractions (IOI19_split) C++17
18 / 100
155 ms 10744 KB
#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

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;
            ^~~~~~
# Verdict Execution time Memory Grader output
1 Correct 7 ms 2680 KB ok, correct split
2 Correct 7 ms 2680 KB ok, correct split
3 Correct 7 ms 2680 KB ok, correct split
4 Correct 6 ms 2680 KB ok, correct split
5 Correct 7 ms 2680 KB ok, correct split
6 Correct 7 ms 2680 KB ok, correct split
7 Correct 118 ms 8184 KB ok, correct split
8 Correct 127 ms 8416 KB ok, correct split
9 Correct 127 ms 8184 KB ok, correct split
10 Correct 112 ms 8184 KB ok, correct split
11 Correct 125 ms 8312 KB ok, correct split
# Verdict Execution time Memory Grader output
1 Correct 7 ms 2680 KB ok, correct split
2 Correct 6 ms 2680 KB ok, correct split
3 Correct 7 ms 2680 KB ok, correct split
4 Correct 129 ms 9464 KB ok, correct split
5 Correct 105 ms 8312 KB ok, correct split
6 Correct 106 ms 8184 KB ok, correct split
7 Correct 122 ms 8184 KB ok, correct split
8 Correct 155 ms 10744 KB ok, correct split
9 Correct 123 ms 8184 KB ok, correct split
10 Correct 65 ms 8944 KB ok, correct split
11 Correct 69 ms 8944 KB ok, correct split
12 Correct 67 ms 8944 KB ok, correct split
# Verdict Execution time Memory Grader output
1 Correct 7 ms 2680 KB ok, correct split
2 Incorrect 102 ms 8312 KB jury found a solution, contestant did not
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 7 ms 2808 KB ok, correct split
2 Correct 6 ms 2680 KB ok, no valid answer
3 Correct 6 ms 2680 KB ok, correct split
4 Correct 6 ms 2680 KB ok, correct split
5 Correct 7 ms 2680 KB ok, correct split
6 Correct 6 ms 2680 KB ok, correct split
7 Correct 7 ms 2680 KB ok, correct split
8 Correct 7 ms 2680 KB ok, correct split
9 Correct 9 ms 2808 KB ok, correct split
10 Correct 9 ms 2936 KB ok, correct split
11 Correct 6 ms 2680 KB ok, correct split
12 Incorrect 9 ms 2936 KB jury found a solution, contestant did not
13 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 7 ms 2680 KB ok, correct split
2 Correct 7 ms 2680 KB ok, correct split
3 Correct 7 ms 2680 KB ok, correct split
4 Correct 6 ms 2680 KB ok, correct split
5 Correct 7 ms 2680 KB ok, correct split
6 Correct 7 ms 2680 KB ok, correct split
7 Correct 118 ms 8184 KB ok, correct split
8 Correct 127 ms 8416 KB ok, correct split
9 Correct 127 ms 8184 KB ok, correct split
10 Correct 112 ms 8184 KB ok, correct split
11 Correct 125 ms 8312 KB ok, correct split
12 Correct 7 ms 2680 KB ok, correct split
13 Correct 6 ms 2680 KB ok, correct split
14 Correct 7 ms 2680 KB ok, correct split
15 Correct 129 ms 9464 KB ok, correct split
16 Correct 105 ms 8312 KB ok, correct split
17 Correct 106 ms 8184 KB ok, correct split
18 Correct 122 ms 8184 KB ok, correct split
19 Correct 155 ms 10744 KB ok, correct split
20 Correct 123 ms 8184 KB ok, correct split
21 Correct 65 ms 8944 KB ok, correct split
22 Correct 69 ms 8944 KB ok, correct split
23 Correct 67 ms 8944 KB ok, correct split
24 Correct 7 ms 2680 KB ok, correct split
25 Incorrect 102 ms 8312 KB jury found a solution, contestant did not
26 Halted 0 ms 0 KB -