제출 #1335183

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1335183		trandaihao5555	Stations (IOI20_stations)	C++20	5 / 100	416 ms	632 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 & b, int & a,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 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;
    cnt = -1;
    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();
    }
}

컴파일 시 표준 에러 (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:97:1: warning: control reaches end of non-void function [-Wreturn-type]
   97 | }
      | ^

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