oj.uz

Submission #321870

# Submission time Handle Problem Language Result Execution time Memory
321870 2020-11-13T13:24:51 Z akobi Stations (IOI20_stations) C++14
0 / 100
 915 ms 884 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<(int)(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<(int)(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<(int)(c.size())-1; i++)
            if (t<c[i+1])
                return i;
        return c.size()-1;
    }
    return -1;
}
// 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;
// }

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 512 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 463 ms 764 KB Wrong query response.
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

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

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 915 ms 868 KB Output is correct
2 Incorrect 695 ms 868 KB Wrong query response.
3 Halted 0 ms 0 KB -

Subtask #5
0 / 61.0

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