Submission #1053669

#	Time	Username	Problem	Language	Result	Execution time	Memory
1053669		nightfal	Stations (IOI20_stations)	C++17	8 / 100	513 ms	684 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;
}

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]);
    }
    // print(g);
    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;}
        }
    }
    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 = 2;
    if (subtask==1) {
        for(int next: c)
            if (s<t && s<next) return next;
            else if (s>t && s>next) return next;
        }
    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;
    }
}

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 'std::vector<int> label(int, int, std::vector<int>, std::vector<int>)':
stations.cpp:41:13: warning: unused variable 'prev' [-Wunused-variable]
   41 |         int prev = node;
      |             ^~~~
stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:75:1: warning: control reaches end of non-void function [-Wreturn-type]
   75 | }
      | ^

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