oj.uz

Submission #531302

# Submission time Handle Problem Language Result Execution time Memory
531302 2022-02-28T11:20:50 Z antonioqbab Stations (IOI20_stations) C++14
0 / 100
 800 ms 656 KB 
#include <bits/stdc++.h>
#include <stations.h>

using namespace std;

vector<int> label(int n, int k, vector<int> u, vector<int> v){
    int t = 0;
    vector<vector<int>> G(n);
    vector<int> sol(n);
    for(int i=0;i<n-1;++i){
        G[u[i]].emplace_back(v[i]);
        G[v[i]].emplace_back(u[i]);
    }
    function<void(int,int,int)> dfs=[&](int node, int last, int lvl){
    if(!lvl)
        sol[node]=++t;
    for(auto x:G[node])
        if(x!=last)
            dfs(x,node,lvl^1);
    if(lvl)
        sol[node]=++t;
    };
    dfs(0,-1,0);
    return sol;
}

int find_next_station(int s, int f, vector<int> adj){
    int tins, touts, ft;
    int isin=1;
    for(auto x:adj)
        if(x>=s)
            isin=0;
    if(isin)
        tins=s, ft=*max(adj.begin(), adj.end()), touts=ft-1;
    else
        touts=s, ft=*min(adj.begin(),adj.end()), tins=ft+1;
    if(tins<=f&&f<=touts){
        int last = s;
        if(isin)
            sort(adj.begin(),adj.end());
        else
            sort(adj.begin(),adj.end(),greater<int>());
        for(auto x:adj){
            int curtin, curtout;
            if(isin)
                curtout=x, curtin=last+1, last=x;
            else
                curtin=x, curtout=last-1, last=x;
            if(curtin<=f&&f<=curtout)
                return x;
        }
    }
    return ft;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 16.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 61.0

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