Submission #321861

# Submission time Handle Problem Language Result Execution time Memory
321861 2020-11-13T13:08:40 Z akobi Stations (IOI20_stations) C++14
0 / 100
968 ms 736 KB
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define F first
#define S second
using namespace std;
vector<int> label(int n, int k, vector<int> u, vector<int> v)
{
    vector< vector<int> > edge;
    vector<int> t,p,fix,anss;
    vector< pair<int,int> >ans;
    for (int i=0; i<n; i++)
    {
        edge.pb(t);
        p.pb(0);
        fix.pb(0);
        anss.pb(0);
    }
    for (int i=0; i<n-1; i++)
    {
        edge[u[i]].pb(v[i]);
        edge[v[i]].pb(u[i]);
    }
    p[0]=-1;
    int c=0,cnt=0,l=0;
    while (c>=0)
    {
        int inn=cnt++,out=0,bbb=0;
        fix[c]=1;
        if (!l)
            ans.pb(mp(inn,c));
        for (int i=0; i<edge[c].size(); i++)
        {
            if (edge[c][i]!=p[c] && fix[ edge[c][i] ]==0)
            {
                p[ edge[c][i] ]=c;
                c=edge[c][i];
                bbb=1;
                break;
            }
        }
        if (bbb)
        {
            l=(l+1)%2;
            continue;
        }
        out=cnt++;
        if (l)
            ans.pb(mp(out,c));
        c=p[c];
        l=(l+1)%2;
    }
    sort(ans.begin(),ans.end());
    for (int i=0; i<n; i++)
        anss[ans[i].S]=i;
    return anss;
}
int find_next_station(int s, int t, vector<int> c)
{
    if (s<c[0])
    {
        //in
        if (t<s || t>c[c.size()-2])
            return c[c.size()-1];
        for (int i=0; i<c.size()-1; i++)
            if (t<=c[i])
                return i;
    }
    else
    {
        //out
        if (t>s || t<c[1])
            return c[0];
        for (int i=1; i<c.size(); i++)
            if (t>=c[i])
                return i;
    }
}

Compilation message

stations.cpp: In function 'std::vector<int> label(int, int, std::vector<int>, std::vector<int>)':
stations.cpp:32:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |         for (int i=0; i<edge[c].size(); i++)
      |                       ~^~~~~~~~~~~~~~~
stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:65:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |         for (int i=0; i<c.size()-1; i++)
      |                       ~^~~~~~~~~~~
stations.cpp:74:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |         for (int i=1; i<c.size(); i++)
      |                       ~^~~~~~~~~
stations.cpp:78:1: warning: control reaches end of non-void function [-Wreturn-type]
   78 | }
      | ^
# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 628 KB Invalid labels (duplicates values). scenario=0, label=0
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 492 KB Invalid labels (duplicates values). scenario=0, label=0
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 492 KB Invalid labels (duplicates values). scenario=1, label=0
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 968 ms 736 KB Wrong query response.
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 620 KB Invalid labels (duplicates values). scenario=1, label=0
2 Halted 0 ms 0 KB -