제출 #1104729

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1104729		SoMotThanhXuan	Valley (BOI19_valley)	C++17	59 / 100	60 ms	15176 KiB

valley

// absolutely incredible
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = a; i <= b; ++i)
#define REP(i, a, b) for(int i = a; i >= b; --i)
#define left _________left
#define right _________right
#define NAME ""
const int mod = 1e9 + 7;
bool maximize(int &u, int v){
    if(v > u){
        u = v;
        return true;
    }
    return false;
}
bool minimize(int &u, int v){
    if(v < u){
        u = v;
        return true;
    }
    return false;
}
bool maximizell(long long &u, long long v){
    if(v > u){
        u = v;
        return true;
    }
    return false;
}
bool minimizell(long long &u, long long v){
    if(v < u){
        u = v;
        return true;
    }
    return false;
}
int fastPow(int a, int n){
    if(n == 0) return 1;
    int t = fastPow(a, n >> 1);
    t = 1ll * t * t % mod;
    if(n & 1) t = 1ll * t * a % mod;
    return t;
}
void add(int &u, int v){
    u += v;
    if(u >= mod) u -= mod;
}
void sub(int &u, int v){
    u -= v;
    if(u < 0) u += mod;
}
const int maxN = 1e5 + 5;
int n, q, s, e;
tuple<int, int, int> edge[maxN];
vector<int> adj[maxN];
int spe[maxN];
const long long INFLL = 1e18;
namespace subtask12{
    bool check(){
        return (n <= 100 && q <= 10000) || (n <= 1000 && q <= 1000);
    }
    long long dist[1001][1001];
    void bfs(int st){
        memset(dist[st], -1, sizeof(dist[st]));
        dist[st][st] = 0;
        queue<int> q;
        q.push(st);
        while(!q.empty()){
            int p = q.front();
            q.pop();
            for(int id : adj[p]){
                auto[u, v, w] = edge[id];
                if(v == p) v = u;
                if(dist[st][v] == -1){
                    dist[st][v] = dist[st][p] + w;
                    q.push(v);
                }
            }
        }
    }
    int in[1001], out[1001], timeDFS;
    void dfs(int u = 1){
        in[u] = ++timeDFS;
        for(int id : adj[u]){
            auto[p, v, w] = edge[id];
            if(v == u) v = p;
            if(in[v] == 0){
                dfs(v);
            }
        }
        out[u] = timeDFS;
    }
    bool inside(int u, int v){
        return in[u] <= in[v] && out[u] >= out[v];
    }
    void solve(){
        FOR(i, 1, n)bfs(i);
        dfs();
        while(q--){
            int id, c;
            cin >> id >> c;
            auto[u, v, w] = edge[id];
            long long res = INFLL;
            if(in[u] > in[v])swap(u, v);
            if(!inside(v, c)){
                if(!inside(v, e)){
                    cout << "escaped\n";
                    continue;
                }
                FOR(i, 1, s){
                    if(!inside(v, spe[i]))res = min(res, dist[spe[i]][c]);
                }
                if(res == INFLL)cout << "oo\n";
                else cout << res << '\n';
                continue;
            }
            if(inside(v, e)){
                cout << "escaped\n";
                continue;
            }
            FOR(i, 1, s){
                if(inside(v, spe[i]))res = min(res, dist[spe[i]][c]);
            }
            if(res == INFLL){
                cout << "oo\n";
            }else cout << res << "\n";
        }
    }
}
namespace subtask3{
    bool check(){
        return s == n;
    }
    int in[maxN], out[maxN], timeDFS;
    void dfs(int u = 1){
        in[u] = ++timeDFS;
        for(int id : adj[u]){
            auto[p, v, w] = edge[id];
            if(v == u) v = p;
            if(in[v] == 0){
                dfs(v);
            }
        }
        out[u] = timeDFS;
    }
    bool inside(int u, int v){
        return in[u] <= in[v] && out[u] >= out[v];
    }
    void solve(){
        dfs();
        while(q--){
            int id, c;
            cin >> id >> c;
            auto[u, v, w] = edge[id];
            if(in[u] > in[v])swap(u, v);
            bool ok1 = inside(v, c);
            bool ok2 = inside(v, e);
            if(ok1 == ok2){
                cout << "escaped\n";
            }else cout << "0\n";
        }
    }
}
void solve(){
    cin >> n >> s >> q >> e;
    FOR(i, 1, n - 1){
        int u, v, w;
        cin >> u >> v >> w;
        edge[i] = {u, v, w};
        adj[u].push_back(i);
        adj[v].push_back(i);
    }
    FOR(i, 1, s)cin >> spe[i];
    if(subtask12 :: check()) return subtask12 :: solve();
    if(subtask3 :: check()) return subtask3 :: solve();
}
int main(){
    if(fopen(NAME".inp", "r")){
        freopen(NAME".inp", "r", stdin);
        freopen(NAME".out", "w", stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int t = 1;
//    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

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

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

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