제출 #1281973

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1281973		dex111222333444555	Valley (BOI19_valley)	C++20	23 / 100	100 ms	20444 KiB

valley

#include <bits/stdc++.h>
#define all(v) begin(v), end(v)
#define fi first
#define se second
#define BIT(x, i) (((x) >> (i)) & 1)
#define dbg(x) "[" #x " = " << x << "]"
using namespace std;
const int MAXN = 1e5 + 5, MAXA = 105, LOG = 19;
const long long inf = 1e18 + 23;
template<class X, class Y> bool minimize(X &x, const Y &y){return x > y ? x = y, 1: 0;}
template<class X, class Y> bool maximize(X &x, const Y &y){return x < y ? x = y, 1: 0;}
int numNode, numShop, numQuery, escape, node[MAXN][2], sta[MAXN], fin[MAXN], h[MAXN];
bool shop[MAXN];
long long dist[MAXN][2];
vector<pair<int, int>> adj[MAXN];
pair<int, int> edge[MAXN];

bool checkSub(int u, int r){
    if (u == -1) return 0;
    return sta[r] <= sta[u] && sta[u] <= fin[r];
}

void updateTwo(const int &x, const int &y, const int &t){
    for(int id = 0; id < 2; id++) if (dist[y][id] < inf){
        if (node[x][0] == node[y][id] || node[x][1] == node[y][id]) continue;
        if (dist[x][0] > dist[y][id]){
            dist[x][1] = dist[x][0];
            node[x][1] = node[x][0];
            dist[x][0] = dist[y][id];
            node[x][0] = node[y][id];
        }else if (minimize(dist[x][1], dist[y][id])) {
            node[x][1] = node[y][id];
        }
    }
}

void dfsRoot(int u, int par = 0){
    sta[u] = ++sta[0];
    if (shop[u]){
        dist[u][0] = 0; node[u][0] = u;
    }
    for(pair<int, int> x: adj[u]) if (x.fi != par){
        int v = x.fi, w = x.se; h[v] = h[u] + 1;
        dfsRoot(v, u);
        if (shop[u]) continue;
        dist[v][0] += w; dist[v][1] += w;
        updateTwo(u, v, 1);
        dist[v][0] -= w; dist[v][1] -= w;
    }
    fin[u] = sta[0];
}

void dfsLeaf(int u, int par = 0){
    for(pair<int, int> x: adj[u]) if (x.fi != par){
        int v = x.fi, w = x.se;
        dist[u][0] += w; dist[u][1] += w;
        updateTwo(v, u, 2);
        dist[u][0] -= w; dist[u][1] -= w;
        dfsLeaf(v, u);
    }
}

void input(){
    cin >> numNode >> numShop >> numQuery >> escape;
    int u, v, w;
    for(int i = 1; i < numNode; i++){
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
        edge[i] = {u, v};
    }
    for(int i = 1; i <= numShop; i++){
        int x; cin >> x;
        shop[x] = 1;
    }
}


bool check(int u, int v, int x, int y){
    if (h[x] < h[y]) swap(x, y);
    int sum = checkSub(u, x) + checkSub(v, x);
    return sum % 2 == 0;
}

void solve(){
    memset(dist, 0x3f, sizeof dist);
    memset(node, -1, sizeof node);
    dfsRoot(1);
    dfsLeaf(1);
    while(numQuery--){
        int id, u; cin >> id >> u;
        int x = edge[id].fi, y = edge[id].se;
        if (check(u, escape, x, y)) cout << "escaped\n";
        else{
            bool flag = 0;
            for(int i = 0; i < 2 && !flag; i++) if (node[u][i] != -1) {
               if (check(u, node[u][i], x, y)){
                    flag = 1;
                    cout << dist[u][i] << '\n';
               }
           }
            for(pair<int, int> tmp: adj[u]){
                int v = tmp.fi, w = tmp.se;
                if ((edge[id].fi == u && edge[id].se == v) || (edge[id].fi == v && edge[id].se == u)) continue;
                if (flag) break;
               for(int i = 0; i < 2 && !flag; i++) if (node[v][i] != -1) {
                   if (check(v, node[v][i], x, y)){
                        flag = 1;
                        cout << dist[v][i] + w << '\n';
                   }
               }
            }
           if (!flag) cout << "oo\n";
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    if (fopen("test.inp", "r")){
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }
    input();
    solve();
    #define TIME (1.0 * clock() / CLOCKS_PER_SEC)
    cerr << TIME << ".s\n";
}

컴파일 시 표준 에러 (stderr) 메시지

valley.cpp: In function 'int main()':
valley.cpp:121:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  121 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:122:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  122 |         freopen("test.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 9
• Subtask 2: 0 / 27
• Subtask 3: 23 / 23
• Subtask 4: 0 / 41