제출 #586660

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
586660		MohamedFaresNebili	기지국 (IOI20_stations)	C++14	100 / 100	869 ms	792 KiB

stations

#include <bits/stdc++.h>
/// #include "stations.h"
/// #pragma GCC optimize ("Ofast")
/// #pragma GCC target ("avx2")
/// #pragma GCC optimize("unroll-loops")
 
        using namespace std;
 
        int timer;
        vector<int> key, adj[1001];
        void dfs(int v, int p, int dep) {
            if(dep == 0) key[v] = timer++;
            for(auto u : adj[v]) {
                if(u == p) continue;
                dfs(u, v, 1 - dep);
            }
            if(dep == 1) key[v] = timer++;
        }
 
        vector<int> label(int N, int K, vector<int> U, vector<int> V) {
            timer = 0; key.assign(N, 0);
            for(int l = 0; l < N; l++) adj[l].clear();
            for(int l = 0; l < N - 1; l++) {
                int X = U[l], Y = V[l];
                adj[X].push_back(Y), adj[Y].push_back(X);
            }
            dfs(0, 0, 0);
            return key;
        }
        int find_next_station(int S, int T, vector<int> C) {
            if(C.size() == 1) return C[0];
            bool tin = 1; int N = C.size(); T *= 2;
            for(auto u : C) tin &= (u > S);
            if(tin) {
                int I = 2 * S, O;
                if(I == 0) O = 2 * C[N - 1] + 1;
                else O = 2 * C[N - 2] + 1;
                if(T < I || T > O) return C[N - 1];
                if(I != 0) N--;
 
                vector<pair<int, int>> A(N);
                for(int l = 1; l < N; l++) {
                    A[l].second = C[l] * 2;
                    A[l].first = C[l - 1] * 2 + 1;
                }
                A[0] = {S * 2 + 1, 2 * C[0]};
                for(int l = 0; l < N; l++) {
                    I = A[l].first, O = A[l].second;
                    if(T >= I && T <= O)
                        return C[l];
                }
            }
            else {
                int I = 2 * C[1] - 1, O = 2 * S;
                if(T < I || T > O) return C[0];
                vector<pair<int, int>> A(N);
                for(int l = 1; l < N - 1; l++) {
                    A[l].first = C[l] * 2;
                    A[l].second = C[l + 1] * 2 - 1;
                }
                A[N - 1] = {C[N - 1] * 2, O - 1};
                for(int l = 1; l < N; l++) {
                    I = A[l].first, O = A[l].second;
                    if(T >= I && T <= O)
                        return C[l];
                }
            }
        }

컴파일 시 표준 에러 (stderr) 메시지

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

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