Submission #804948

#	Time	Username	Problem	Language	Result	Execution time	Memory
804948		PixelCat	Stations (IOI20_stations)	C++14	0 / 100	596 ms	548 KiB

stations

#include "stations.h"

#ifdef NYAOWO
#include "stub.cpp"
#endif

#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
// #define int LL
using namespace std;
using i32 = int32_t;
using LL = long long;
using pii = pair<int, int>;

const int MAXN = 1000;

vector<int> adj[MAXN + 10];
int ids[MAXN + 10];
int siz[MAXN + 10];
int cur_id;

void dfs1(int n, int p) {
    ids[n] = cur_id;
    cur_id++;
    siz[n] = 0;
    for(auto &i:adj[n]) if(i != p) {
        dfs1(i, n);
        siz[n] += siz[i] + 1;
    }
}

int encode(int id, int sz) {
    return id * MAXN + sz;
}
int encode(pii p) {
    return encode(p.F, p.S);
}
pii decode(int x) {
    return pii(x / MAXN, x % MAXN);
}

std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
    For(i, 0, n - 1) {
        adj[i].clear();
    }
    int m = sz(u);
    For(i, 0, m - 1) {
        adj[u[i]].eb(v[i]);
        adj[v[i]].eb(u[i]);
    }
    // cur_id = 0;
    // dfs1(0, 0);
    vector<int> labels(n);
    For(i, 0, n - 1) labels[i] = i;
    return labels;
}

int find_next_station(int s, int t, std::vector<int> c) {
    if(sz(c) == 1) return c[0];
    
    int id = (c[1] - 1) / 2;
    int t2 = t;
    while(t2) {
        if(t2 == id * 2 + 1) return t2;
        if(t2 == id * 2 + 2) return t2;
        t2 /= 2;
    }
    return (id - 1) / 2;
    
    // vector<pii> v;  // {id, sz}
    // for(auto &x:c) v.eb(decode(x));
    // sort(all(v));

    // int n = sz(v);

    // int id = v[1].F - 1;
    // int sz = 0;
    // For(i, 1, n - 1) sz += v[i].S + 1;
    
    // pii pt = decode(t);
    // if(pt.F < id || pt.F > id + sz) return encode(v[0]);
    // For(i, 0, n - 2) {
    //     if(pt.F < v[i + 1].F) return encode(v[i]);
    // }
    // return encode(v[n - 1]);
}

/*

1
5 10
0 1
1 2
1 3
2 4
2
2 0 1
1 3 3

*/

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