Submission #364914

#	Time	Username	Problem	Language	Result	Execution time	Memory
364914		mario05092929	Stations (IOI20_stations)	C++14	100 / 100	1085 ms	1448 KiB

stations

#include "stations.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define all(v) v.begin(),v.end()
#pragma gcc optimize("O3")
#pragma gcc optimize("Ofast")
#pragma gcc optimize("unroll-loops")
using namespace std;
const int INF = 1e9;
const int TMX = 1 << 18;
const long long llINF = 2e18;
const long long mod = 1e9+7;
const long long hashmod = 100003;
const int MAXN = 100000;
const int MAXM = 1000000;
typedef long long ll;
typedef long double ld;
typedef pair <int,int> pi;
typedef pair <ll,ll> pl;
typedef vector <int> vec;
typedef vector <pi> vecpi;
typedef long long ll;
int co,n,k;
vec v[1005];
vec la;

void dfs(int x,int pr,int dep) {
    if(dep % 2) la[x] = ++co;
    for(int i : v[x]) if(i^pr) dfs(i,x,dep+1);
    if(dep % 2 == 0) la[x] = ++co;
}

std::vector<int> label(int N, int K, std::vector<int> u, std::vector<int> u2) {
    n = N, k = K;
    for(int i = 0;i < n;i++) v[i].clear();
    for(int i = 0;i < n-1;i++) v[u[i]].pb(u2[i]), v[u2[i]].pb(u[i]);
    la.resize(n,0);
    co = 0; dfs(1,-1,1);
    return la;
}

int find_next_station(int s, int t, std::vector<int> c) {
    sort(all(c));
    int isin = (s < c[0]), isroot = (s == 1);
    int par = -1,m = c.size();
    if(isin) {
        par = c.back();
        m--;
        int l = s+1;
        for(int i = 0;i < m;i++) {
            if(l <= t&&t <= c[i]) return c[i];
            l = c[i]+1;
        }
        return par;
    }
    else {
        par = c[0];
        for(int i = 0;i < m-1;i++) c[i] = c[i+1];
        m--;
        c[m] = s;
        for(int i = 0;i < m;i++) {
            if(c[i] <= t&&t < c[i+1]) return c[i];
        }
        return par;
    }

}

Compilation message (stderr)

stations.cpp:7: warning: ignoring #pragma gcc optimize [-Wunknown-pragmas]
    7 | #pragma gcc optimize("O3")
      | 
stations.cpp:8: warning: ignoring #pragma gcc optimize [-Wunknown-pragmas]
    8 | #pragma gcc optimize("Ofast")
      | 
stations.cpp:9: warning: ignoring #pragma gcc optimize [-Wunknown-pragmas]
    9 | #pragma gcc optimize("unroll-loops")
      | 
stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:46:28: warning: unused variable 'isroot' [-Wunused-variable]
   46 |     int isin = (s < c[0]), isroot = (s == 1);
      |                            ^~~~~~

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