oj.uz

Submission #321865

# Submission time Handle Problem Language Result Execution time Memory
321865 2020-11-13T13:18:47 Z akobi Stations (IOI20_stations) C++14
0 / 100
 869 ms 996 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=0,out=0,bbb=0;
        if (fix[c]==0)
        {
            inn=cnt++;
            if (!l)
            {
                ans.pb(mp(inn,c));
                // cout<<inn<<" "<<c<<endl;
            } 
        }
        fix[c]=1;
        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));
            // cout<<out<<" "<<c<<endl;
        }
        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;
    }
}
// int n,k,a,b;
// vector<int> u,v,ans;
// int main()
// {
//     cin>>n>>k;
//     for (int i=0; i<n-1; i++)
//     {
//         cin>>a>>b;
//         u.pb(a);
//         v.pb(b);
//     }
//     ans=label(n,k,u,v);
//     for (int i=0; i<n; i++)
//         cout<<ans[i]<<" ";
//     cout<<endl;
//     return 0;
// }

Compilation message

stations.cpp: In function 'std::vector<int> label(int, int, std::vector<int>, std::vector<int>)':
stations.cpp:39:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |         for (int i=0; i<edge[c].size(); i++)
      |                       ~^~~~~~~~~~~~~~~
stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:75:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |         for (int i=0; i<c.size()-1; i++)
      |                       ~^~~~~~~~~~~
stations.cpp:84:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |         for (int i=1; i<c.size(); i++)
      |                       ~^~~~~~~~~
stations.cpp:88:1: warning: control reaches end of non-void function [-Wreturn-type]
   88 | }
      | ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 525 ms 756 KB Wrong query response.
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 429 ms 736 KB Wrong query response.
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 516 ms 756 KB Wrong query response.
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 869 ms 868 KB Wrong query response.
2 Halted 0 ms 0 KB -

Subtask #5
0 / 61.0

# Verdict Execution time Memory Grader output
1 Incorrect 494 ms 996 KB Wrong query response.
2 Halted 0 ms 0 KB -