Submission #781215

#	Time	Username	Problem	Language	Result	Execution time	Memory
781215		bane	Stations (IOI20_stations)	C++17	27.55 / 100	750 ms	716 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] = 10000 * 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] / 10000;
				int out = c[i] % 1000;

				if (in <= s/10000 && out >= s%10000){
					index = i;
					//parent
					continue;
				}

				if (t / 10000 >= in && t / 10000 <= 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: 17.5505 / 61