Submission #1335159

#	Time	Username	Problem	Language	Result	Execution time	Memory
1335159		trandaihao5555	Stations (IOI20_stations)	C++20	0 / 100	409 ms	620 KiB

stations

#include "stations.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define mp make_pair

typedef vector<int> vi;
typedef pair<int,int> pii;

const int MaxN = 1e6+7;
const int MAX = 1e3;

pii e[MaxN];
vi adj[MaxN],c;
int n,k,s,t,Tin[MaxN],Tout[MaxN],cnt = -1;

void dfs(int u,int p) {
    Tin[u] = ++cnt;
    for(int v : adj[u]) {
        if (v == p) continue;
        dfs(v,u);
    }
    Tout[u] = cnt;
}

namespace sub1 {
    bool label_check() {
        for(int i=0;i<n;i++) {
            if (adj[i].size() > 2) return false;
        }
        return true;
    }


    vi label() {
        for(int i=0;i<n;i++) {
            if (adj[i].size() != 1) continue;
            dfs(i,-1);
            break;
        }
        vi res;
        for(int i=0;i<n;i++) {
            res.pb(Tin[i]);
        }
        return res;
    }

    void CalcLabel(int & a, int & b,int c) {
        a = min(a,c);
        b = max(b,c);
    }

    bool find_check() {
        int maxLabel = s;
        int minLabel = s;
        CalcLabel(maxLabel,minLabel,t);
        for(int x : c) CalcLabel(maxLabel,minLabel,x);
        return minLabel == 0 && maxLabel <= 1000;
    }

    int find_next_station() {
        if (s > t) swap(s,t);
        for (int x : c) {
            if (s <= x && x <= t) return x;
        }
    }
}

std::vector<int> label(int N, int K, std::vector<int> U, std::vector<int> V) {
    n = N;
    k = K;
    for(int i=0;i<U.size();i++) {
        int u = U[i];
        int v = V[i];
        adj[u].pb(v);
        adj[v].pb(u);
        e[i] = mp(u,v);
    }
    vi label;
    if (sub1::label_check()) {
        label = sub1::label();
    }
    for(int i=0;i<n;i++) adj[i].clear();
    return label;
}

int find_next_station(int S, int T, std::vector<int> C) {
    s = S;
    t = T;
    c = C;
    if (sub1::find_check()) {
        return sub1::find_next_station();
    }
}

Compilation message (stderr)

stations.cpp: In function 'int sub1::find_next_station()':
stations.cpp:68:5: warning: control reaches end of non-void function [-Wreturn-type]
   68 |     }
      |     ^
stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:96:1: warning: control reaches end of non-void function [-Wreturn-type]
   96 | }
      | ^

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