Submission #1053840

#	Time	Username	Problem	Language	Result	Execution time	Memory
1053840		nightfal	Stations (IOI20_stations)	C++17	16 / 100	537 ms	1192 KiB

stations

// #include "stations.h"
#include <cstdio>
#include <iostream>
#include <cassert>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;


template <typename T> void print(T elem) {cout << elem << " ";}
template <typename T> void print(vector<T> &v) {for(auto elem: v) print(elem); cout << endl;};
template <typename T> void print(vector<vector<T>> &v) {for(auto elem: v) print(elem); cout << endl;};

bool subtask1(vector<vector<int>> &g) {
    int n = g.size();
    for(auto elem: g)
        if (elem.size() > 2) return false;
    return true;
}
bool subtask2(vector<int> &u, vector<int> &v) {
    int m = u.size();
    for(int i=0; i<m; i++)
        if (!(u[i]==i+1 && v[i]==i/2 || u[i]==i/2 && v[i]==i+1))
            return false;
    return true;
}
bool subtask3(vector<vector<int>> &g) {
    int n=g.size(), cnt=0;
    for(auto elem: g)
        if(elem.size()>2) cnt++;
    if (cnt<=1) return true;
    return false;
}
void genLabels(int key, int node, vector<int> &labels, vector<vector<int>> &g) {
    labels[node]=key*1000+1;
    for(int i=2; i<1000; i++) {
        bool terminal = true;
        for(int next: g[node]) {
            if(labels[next]==-1) {labels[next] = 1000*key+i; node = next; terminal=false;}
        }
        if (terminal) return;
    }
}
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
	std::vector<int> labels(n,-1);
    vector<vector<int>> g(n);
    for (int i=0; i<n-1; i++) {
        g[u[i]].push_back(v[i]);
        g[v[i]].push_back(u[i]);
    }
    if (subtask3(g)) {
        int root = 0;
        for(int i=0; i<n; i++)
            if(g[i].size() > 2)  {root = i; break;}
            labels[root] = 1000;
        for(int i=0; i<g[root].size(); i++) {
            int child = g[root][i];
            genLabels(i+1, child, labels, g);
        }
    }
    else if (subtask1(g)) {
        int node = 0;
        for (int i=0; i<n; i++)
            if(g[i].size()==1) node = i;
        int prev = node;
        for (int i=0; i<n; i++) {
            labels[node] = i;
            for(int next: g[node])
                if(labels[next]== -1) {node = next;}
        }
    }
    else if (subtask2(u,v)) {
        for(int i=0; i<n; i++)
            labels[i] = i;
    }

    // print(labels);
	return labels;
}
bool ancestor(int s, int t) {
    if (s==0) return true;
    while (t) {
        if (s==t) return true;
        t = (t-1)>>1;
    }
    return false;
}
int find_next_station(int s, int t, std::vector<int> c) {
    int subtask = 0;

    if (s>1000 || t>1000) subtask=3;
    else {
        if (s==0) {
            if (c.size()==1) subtask = 1;
            else if (c.size()==2) subtask = 2;
        }
        else if (s==1) {
            if (t==0) return 0;
            else {
                subtask = 2;
                for(int elem: c) 
                    if(elem == 2) {subtask=1; break;}
            }
        }
        else {
            subtask = 1;
            for(int i=0; i<c.size(); i++)
                if(!(c[i]==s-1 || c[i]==s+1)) {subtask = 2; break;}
        }
    }

    if (subtask==1) {
        for(int next: c)
            if (s<t && s<next) return next;
            else if (s>t && s>next) return next;
        }
    else if (subtask==2) {
        if (ancestor(2*s+1,t)) return 2*s+1;
        else if (ancestor(2*s+2,t)) return 2*s+2;
        else return (s-1)/2;
    }
    else if (subtask==3) {
        if (s==1000) return (t/1000)*1000+1;
        if (s/1000 == t/1000) {
            if (s<t) return s+1;
            else return s-1;
        }
        else { 
            if (s%1000==1) return 1000;
            else return s-1;
        }
    }
}

Compilation message (stderr)

stations.cpp: In function 'bool subtask1(std::vector<std::vector<int> >&)':
stations.cpp:16:9: warning: unused variable 'n' [-Wunused-variable]
   16 |     int n = g.size();
      |         ^
stations.cpp: In function 'bool subtask2(std::vector<int>&, std::vector<int>&)':
stations.cpp:24:25: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   24 |         if (!(u[i]==i+1 && v[i]==i/2 || u[i]==i/2 && v[i]==i+1))
stations.cpp: In function 'bool subtask3(std::vector<std::vector<int> >&)':
stations.cpp:29:9: warning: unused variable 'n' [-Wunused-variable]
   29 |     int n=g.size(), cnt=0;
      |         ^
stations.cpp: In function 'std::vector<int> label(int, int, std::vector<int>, std::vector<int>)':
stations.cpp:54:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   54 |         for(int i=0; i<n; i++)
      |         ^~~
stations.cpp:56:13: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   56 |             labels[root] = 1000;
      |             ^~~~~~
stations.cpp:57:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |         for(int i=0; i<g[root].size(); i++) {
      |                      ~^~~~~~~~~~~~~~~
stations.cpp:66:13: warning: unused variable 'prev' [-Wunused-variable]
   66 |         int prev = node;
      |             ^~~~
stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:108:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |             for(int i=0; i<c.size(); i++)
      |                          ~^~~~~~~~~
stations.cpp:134:1: warning: control reaches end of non-void function [-Wreturn-type]
  134 | }
      | ^

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