제출 #1244551

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1244551		qwusha	Stations (IOI20_stations)	C++20	10 / 100	302 ms	24156 KiB

stations

#include "stations.h"

#include <iostream>
#include <bits/stdc++.h>

#define fi first
#define se second

using namespace std;

int inf = 1e9 + 7;

vector<vector<int>> g;
vector<int> par;
vector<set<int>> st;

void dfs(int v, int p = -1) {
    par[v] = p;
    st[v].insert(v);
    for (auto u : g[v]) {
        if (u != p) {
            dfs(u, v);
            for (auto el : st[u]) {
                st[v].insert(el);
            }
        }
    }
}

vector<int> label(int n, int k, vector<int> v, vector<int> u) {
    vector<int> res(n);
    g.assign(n, {});
    par.assign(n , -1);
    st.assign(n, {});
    for (int i = 0; i < n - 1; i++) {
        g[v[i]].push_back(u[i]);
        g[u[i]].push_back(v[i]);
    }
    dfs(0);
    for (int i = 0; i < n; i++) {
        for (auto el : st[i]) {
            res[i] += (1 << el);
        }
    }
    return res;
}


bool subs(set<int> s1, set<int> s2) {
    bool ok = 1;
    for (auto el : s1) {
        if (s2.find(el) == s2.end()) {
            ok = 0;
        }
    }
    return ok;
}


int find_next_station(int s, int t, vector<int> c) {
    if (c.size() == 1) {
        return c[0];
    }
    set<int> sst;
    for (int i = 0; i < 8; i++) {
        if ((s >> i) & 1) {
            sst.insert(i);
        }
    }
    set<int> tst;
    for (int i = 0; i < 8; i++) {
        if ((t >> i) & 1) {
            tst.insert(i);
        }
    }
    int p = -1;
    for (auto el : c) {
        set<int> elst;
        for (int i = 0; i < 8; i++) {
            if ((el >> i) & 1) {
                elst.insert(i);
            }
        } 
        if (subs(sst, elst)) {
            p = el;
        }
        if (subs(tst, elst) && p != el) {
            return el;
        }
    }
    return p;
}

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