Submission #605381

#	Time	Username	Problem	Language	Result	Execution time	Memory
605381		MohamedAliSaidane	Stations (IOI20_stations)	C++14	0 / 100	953 ms	548 KiB

stations

#include <bits/stdc++.h>

    using namespace std;

    typedef long long ll;

    typedef pair<int,int> pii;
    typedef pair<ll,ll> pll;

    typedef vector<int> vi;
    typedef vector<ll> vll;
    typedef vector<pii> vpi;
    typedef vector<pll> vpl;

    #define pb push_back
    #define popb pop_back
    #define all(x) (x).begin(),(x).end()
    #define ff first
    #define ss second
    vi label(int n, int k, vi u, vi v)
    {
        vi rep(n);
        rep.assign(n, - 1);
        vi adj[n];
        for(int i = 0 ; i <n -  1; i ++)
        {
            adj[u[i]].pb(v[i]);
            adj[v[i]].pb(u[i]);
        }
        int cor = 0;
        for(int i=  0 ; i < n; i ++ )
        {
            if(adj[i].size() > adj[cor].size())
            {
                cor = i;
            }
        }
        rep[cor] = 0;
        for(int i = 0; i < (int)(adj[cor].size()); i ++)
        {
            rep[adj[cor][i]] = 1000 * i + 1;
            queue<pii> q;
            q.push({adj[cor][i], rep[adj[cor][i]]});
            while(!q.empty())
            {
                int node = q.front().ff;
                int d = q.front().ss;
                q.pop();
                rep[node] = d;
                for(auto e: adj[node])
                {
                    if(rep[e] == -1)
                    {
                        rep[e] = d + 1;
                        q.push({e, d+ 1});
                    }
                }
            }
        }
        return rep;
    }
    int find_next_station(int s, int t, vi c)
    {
        if(s/1000 == t/1000)
        {
            if(s > t)
            {
                int mini = c[0];
                for(auto e: c)
                    mini = min(mini, e);
                return mini;
            }
            else
            {
                int maxi = c[0];
                for(auto e: c)
                    maxi = max(maxi, e);
                return maxi;
            }
        }
        else
        {
            if(s == 0)
            {
                for(auto e: c)
                {
                    if(e/1000 == t/1000)
                        return e;
                }
            }
            int mini = c[0];
            for(auto e: c)
                mini = min(mini, e);
            return mini;
        }
    }

• Subtask 1: 0 / 5
• Subtask 2: 0 / 8
• Subtask 3: 0 / 16
• Subtask 4: 0 / 10
• Subtask 5: 0 / 61