제출 #781232

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
781232		bane	기지국 (IOI20_stations)	C++17	100 / 100	857 ms	708 KiB

stations

    #include "stations.h"
    #include<bits/stdc++.h>
     
    using namespace std;
     
    const int Nax = 1005;
     
    class Undirected_Graph{
    	public:
    		
    		int N, Timer = 0;
    		vector<vector<int>>adj;
    		vector<int>in;
     
    		Undirected_Graph(int _N):N(_N){
    			adj.resize(N);
    			in.resize(N);
    		}
     
    		inline void Add_Edge(int A, int B){
    			adj[A].push_back(B);
    			adj[B].push_back(A);
    		}
     
    		void Depth_First_Search(int Node, int Parent, int even = 1){
    			if(even)in[Node] = Timer++;
    			for (int& Next : adj[Node]){
    				if (Next == Parent)continue;
    				Depth_First_Search(Next,Node,even^1);
    			}
					if (!even)in[Node] = Timer++;
    		}
     
    };
     
     
    std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
    	std::vector<int> labels(n);
    	Undirected_Graph G(n);
     
    	for (int i = 0; i < n - 1; i++){
    		G.Add_Edge(u[i],v[i]);
    	}
     
    	G.Depth_First_Search(0,0);
     
    	labels = G.in;
     
    	return labels;
    }
     
    int find_next_station(int s, int t, std::vector<int> c) {

			if (c.back() < s){
				//S is out
				for (int i = c.size() - 1 ; i >=0; i--){
					if (t >= c[i] && s >= t)return c[i];
				}
				//parent is lowest even
				return c[0];
			}else{
				// S is in
				for (int i = 0; i + 1 < (int)c.size(); i++){
					if (t >= s&& t <= c[i])return c[i];
				}

				return c.back();
			}
    }

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