제출 #496315

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
496315		kingline	Valley (BOI19_valley)	C++17	36 / 100	3075 ms	10360 KiB

valley

/*#pragma GCC optimize("O3")
#pragma GCC target ("avx2")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")*/
#include <bits/stdc++.h>
#define file(data) freopen(data".in", "r", stdin); freopen(data".out", "w", stdout);
#define pb push_back
#define all(data) data.begin(), data.end()
#define endl '\n'
#define ll long long
//#define int long long
#define pii pair < int, int >

using namespace std;

const int N = 2e5 + 5;

int n, s, q, e, a[N], b[N], w[N], block;
bool shop[N], escape;
vector < pair < int, int > > g[N];
long long ans;

void found(int v, long long sum, int pr) {
    if(shop[v]) {
        ans = min(sum, ans);
    }
    if(v == e) {
        escape = 1;
        return;
    }
    for(int i = 0; i < g[v].size(); i++) {
        int to = g[v][i].first, len = g[v][i].second;
        if(to != pr) {
            if((a[block] == v && b[block] == to) || (a[block] == to && b[block] == v)) {
                continue;
            }
            found(to, sum + len, v);
        }
    }
}

main() {
    //file("pieaters");
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> s >> q >> e;
    for(int i = 1; i < n; i++) {
        cin >> a[i] >> b[i] >> w[i];
        g[a[i]].pb({b[i], w[i]});
        g[b[i]].pb({a[i], w[i]});
    }
    for(int i = 1; i <= s; i++) {
        int x; cin >> x;
        shop[x] = 1;
    }
    while(q--) {
        int start;
        cin >> block >> start;
        escape = 0; ans = 1e14 + 1;
        found(start, 0, start);
        if(escape) {
            cout << "escaped\n";
        } else if(ans == 1e14 + 1) {
            cout << "oo\n";
        } else {
            cout << ans << endl;
        }
    }
}

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

valley.cpp: In function 'void found(int, long long int, int)':
valley.cpp:32:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for(int i = 0; i < g[v].size(); i++) {
      |                    ~~^~~~~~~~~~~~~
valley.cpp: At global scope:
valley.cpp:43:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   43 | main() {
      | ^~~~

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