Submission #1292925

#	Time	Username	Problem	Language	Result	Execution time	Memory
1292925		binminh01	LOSTIKS (INOI20_lostiks)	C++20	23 / 100	137 ms	201704 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define double long double
#define sz(a) (int)a.size()
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define pb push_back
#define eb emplace_back
#define open(s) freopen(s, "r", stdin)
#define write(s) freopen(s, "w", stdout)
using pii = pair<int, int>;
using pll = pair<ll, ll>;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<double> vdo;
typedef vector<vdo> vvdo;
typedef vector<string> vs;
typedef vector<pii> vpair;
typedef vector<vpair> vvpair;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<char> vc;
typedef vector<vc> vvc;
typedef priority_queue<int> pq;
typedef priority_queue<int, vi, greater<int>> pqg;
typedef priority_queue<ll> pqll;
typedef priority_queue<ll, vll, greater<ll>> pqgll;
#define For(i, a, b) for (auto i = (a); i < (b); ++i)
#define FOR(i, a, b) for (auto i = (a); i <= (b); ++i)
#define Fore(i, a, b) for (auto i = (a); i >= (b); --i)
#define trav(i, a) for (auto &i: a)
template<class A, class B> bool ckmin(A &a, const B &b) {return a > b ? a = b, 1: 0;}
template<class A, class B> bool ckmax(A &a, const B &b) {return a < b ? a = b, 1: 0;}

constexpr int N = 1000003, inf = 1e9;
int n, m, id[N], h[N], in[N], out[N], eul[21][2*N], tour[N], fi[N], tt, se, LG[2*N];
vpair g[N];
void dfs(int u, int p) {
    in[u] = ++tt, eul[0][++se] = in[u];
    tour[tt] = u, fi[u] = se;
    trav(v,g[u]) if (v.first != p) h[v.first] = h[u] + 1, dfs(v.first, u), eul[0][++se] = in[u];
    out[u] = tt;
}
int lca(int l, int r) {
    l = fi[l], r = fi[r];
    if (l > r) swap(l, r);
    int i = LG[r - l + 1];
    return tour[min(eul[i][l], eul[i][r - (1 << i) + 1])];
}
int dist(int u, int v) {
    return h[u] + h[v] - 2*h[lca(u, v)];
}
bool anc(int u, int v) {
    return in[u] <= in[v] && out[u] >= out[v];
}
bool on_path(int u, int v, int w) {
    //w on u->v?
    return (anc(w, u) || anc(w, v)) && anc(lca(u, v), w);
}
int ver[20], other[20], pos[20], lst[20][20];
int cal(int u, int v, int w, int msk) {
    For(i,0,m) if (!(msk >> i & 1) && (on_path(u, w, other[i]) || on_path(w, v, other[i]))) return inf;
    return dist(u, w) + dist(w, v);
}
int cal(int i, int j, int msk) {
    if ((msk & lst[i][j]) != lst[i][j]) return inf;
    return dist(ver[i], pos[j]) + dist(pos[j], ver[j]);
}
bool c[N], can[20];
ll d[1 << 20][20];
int main() {
    if (fopen("lostik.inp", "r")) freopen("lostik.inp", "r", stdin), freopen("lostik.out", "w", stdout);
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    For(i,2,2*N) LG[i] = LG[i >> 1] + 1;
    int S, T; cin >> n >> S >> T;
    For(i,1,n){
        int u, v, w; cin >> u >> v >> w;
        g[u].eb(v, w), g[v].eb(u, w);
        if (w && !id[w]) pos[m] = w, id[w] = m++;
    }
    dfs(1, 0);
    FOR(i,1,20) FOR(j,1,2*n-(1<<i)) eul[i][j] = min(eul[i - 1][j], eul[i - 1][j + (1 << (i - 1))]);
    queue<int> q; c[S] = 1, q.push(S);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        trav(_,g[u]){
            int v = _.first, w = _.second;
            if (c[v]) continue;
            c[v] = 1, q.push(v);
            if (w && !ver[id[w]]) ver[id[w]] = u, other[id[w]] = v;
        }
    }
    memset(c, 0, sizeof(c));
    c[S] = 1, q.push(S);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        if (u == T) return cout << dist(S, T), 0;
        trav(_,g[u]){
            int v = _.first, w = _.second;
            if (!w && !c[v]) c[v] = 1, q.push(v);
        }
    }
    memset(d, 0x3f, sizeof(d));
    For(i,0,m){
        int x = cal(S, ver[i], pos[i], 0);
        if (x < inf) d[1 << i][i] = x;
    }
    For(i,0,m) For(j,0,m) if (i != j) {
        For(k,0,m) if (on_path(ver[i], pos[j], other[k]) || on_path(pos[j], ver[j], other[k])) lst[i][j]^=1 << k;
    }
    For(msk,1,1<<m) For(i,0,m) if (d[msk][i] < inf) {
        For(j,0,m) if (!(msk >> j & 1)) {
            int x = cal(i, j, msk);
            if (x < inf) ckmin(d[msk^(1 << j)][j], d[msk][i] + x);
        }
    }
    int x = inf;
    For(i,0,m) can[i] = on_path(S, T, other[i]);
    For(msk,1,1<<m){
        bool ok = 1;
        For(i,0,m) if (!(msk >> i & 1) && can[i]) {ok = 0; break;}
        if (!ok) continue;
        For(i,0,m) ckmin(x, d[msk][i] + dist(ver[i], T));
    }
    cout << (x < inf ? x: -1);
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:75:42: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |     if (fopen("lostik.inp", "r")) freopen("lostik.inp", "r", stdin), freopen("lostik.out", "w", stdout);
      |                                   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:75:77: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |     if (fopen("lostik.inp", "r")) freopen("lostik.inp", "r", stdin), freopen("lostik.out", "w", stdout);
      |                                                                      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 23 / 23
• Subtask 2: 0 / 36
• Subtask 3: 0 / 41