Submission #781219

#	Time	Username	Problem	Language	Result	Execution time	Memory
781219		bane	Stations (IOI20_stations)	C++17	10.00 / 100	775 ms	764 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, out;
         
        		Undirected_Graph(int _N):N(_N){
        			adj.resize(N);
    					out.resize(N);
        			in.resize(N);
        		}
         
        		inline void Add_Edge(int A, int B){
        			adj[A].push_back(B);
        			adj[B].push_back(A);
        		}
         
        		inline void Depth_First_Search(int Node, int Parent){
        			in[Node] = Timer++;
        			for (int& Next : adj[Node]){
        				if (Next == Parent)continue;
        				Depth_First_Search(Next,Node);
        			}
    					out[Node] = Timer - 1;
        		}
         
        };
         
         
        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);
         
    			for (int i = 0; i < n; i++){
    				labels[i] = 1000000 * G.in[i] + G.out[i];
    			}
         
        	return labels;
        }
         
        int find_next_station(int s, int t, std::vector<int> c) {
    			int index = 0, n = (int)c.size();
    			for (int i = 0; i < n; i++){
    				int in = c[i] / 1000000;
    				int out = c[i] % 1000000;
     
    				if (in <= s/1000000 && out >= s%1000000){
    					index = i;
    					//parent
    					continue;
    				}
     
    				if (t / 1000000 >= in && t / 1000000 <= out){
    					return c[i];
    				}
    			}
        	return c[index];
        }

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