Submission #781224

#	Time	Username	Problem	Language	Result	Execution time	Memory
781224		bane	Stations (IOI20_stations)	C++17	100 / 100	742 ms	756 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, 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){
						reverse(c.begin(),c.end());
					}
					for (int i = 0; i < (int)c.size(); i++){
						if (t >= min(c[i],s) && t <= max(c[i],s))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