oj.uz

답안 #490607

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
490607 2021-11-28T10:12:19 Z Carmel_Ab1 Valley (BOI19_valley) C++17
100 / 100
 453 ms 57668 KB 
#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

//using namespace __gnu_pbds;
using namespace std;

typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<pl> vpl;
typedef vector<ld> vld;
typedef pair<ld, ld> pld;
typedef vector<pi> vpi;

//typedef tree<ll, null_type, less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
template<typename T>
ostream &operator<<(ostream &os, vector<T> &a) {
    os << "[";
    for (int i = 0; i < ll(a.size()); i++) { os << a[i] << ((i != ll(a.size() - 1) ? " " : "")); }
    os << "]\n";
    return os;
}

#define all(x) x.begin(),x.end()
#define YES out("YES")
#define NO out("NO")
#define out(x){cout << x << "\n"; return;}
#define GLHF ios_base::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL)
#define print(x){for(auto ait:x) cout << ait << " "; cout << "\n";}
#define pb push_back
#define umap unordered_map

template<typename T1, typename T2>
istream &operator>>(istream &is, pair<T1, T2> &p) {
    is >> p.first >> p.second;
    return is;
}

template<typename T1, typename T2>
ostream &operator<<(ostream &os, pair<T1, T2> &p) {
    os << "" << p.first << " " << p.second << "";
    return os;
}

void usaco(string taskname) {
    string fin = taskname + ".in";
    string fout = taskname + ".out";
    const char *FIN = fin.c_str();
    const char *FOUT = fout.c_str();
    freopen(FIN, "r", stdin);
    freopen(FOUT, "w", stdout);
}

template<typename T>
void read(vector<T> &v) {
    int n = v.size();
    for (int i = 0; i < n; i++)
        cin >> v[i];
}

template<typename T>
vector<T> UNQ(vector<T> a) {
    vector<T> ans;
    for (T t: a)
        if (ans.empty() || t != ans.back())
            ans.push_back(t);
    return ans;
}

ll ceil(ll a, ll b) {
    ll ans = a / b;
    if (a % b)ans++;
    return ans;
}

ld log(ld a, ld b) { return log(b) / log(a); }

ll power(ll base, ll exp, ll M = 1e18) {//(base^exp)%M
    ll ans = 1;
    while (exp) {
        if (exp % 2 == 1)ans = ((ans % M) * (base % M)) % M;
        base = ((base % M) * (base % M)) % M;
        exp /= 2;
    }
    return ans;
}

string to_base(int n, int new_base) {
    string s;
    int nn = n;
    while (nn) {
        s += to_string(nn % new_base);
        nn /= new_base;
    }
    reverse(all(s));
    return s;
}

ll gcd(ll a, ll b) {
    if (a < b)swap(a, b);
    if (b == 0)return a;
    return gcd(b, a % b);
}

ll lcm(ll a, ll b) {
    ll x = (a / gcd(a, b));
    return b * x;
}

vl generate_array(ll n, ll mn = 1, ll mx = 1e18 + 1) {
    if (mx == 1e18 + 1)
        mx = n;
    vl ans(n);
    for (int i = 0; i < n; i++)
        ans[i] = (mn + rand() % (mx - mn + 1));
    return ans;
}

string substr(string s, int l, int r) {
    string ans;
    for (int i = l; i <= r; i++)
        ans += s[i];
    return ans;
}


void solve();

int main() {
    GLHF;
    int t = 1;
    //cin >> t;
    while (t--)
        solve();
}

vl a;
vector<vpl> g;
vvl E;
vvi up;
vvl mn;
vi tin,tout,dep;
vl down,dist;

int timer=0,lg=20;
int n, s, q, e;

void dfs(int src,int par){
    tin[src]=++timer;
    if(par!=-1)
        dep[src]=dep[par]+1;
    up[src][0]=par;
    if(a[src])
        down[src]=0;

    for(pi nbr:g[src])
        if(nbr.first!=par) {
            dist[nbr.first]=dist[src]+nbr.second;
            dfs(nbr.first, src);
            down[src]=min(down[src],down[nbr.first]+nbr.second);
        }
    mn[src][0]=down[src]-dist[src];

    tout[src]=timer;
}


ll calc(int r,int u,int v){
    // u is lower
    ll ans=1e18;

    int p=r;
    for(int i=0; i<lg; i++)
        if((dep[p]-dep[v])&(1<<i)){
            ans=min(ans,dist[r]+mn[p][i]);
            p=up[p][i];
        }


    return ans;
}

void solve() {
    cin >> n >> s >> q >> e;

    g.resize(n + 1);

    for(int i=0; i<n-1; i++){
        ll u,v,w;
        cin >> u >> v >> w;
        g[u].pb({v,w});
        g[v].pb({u,w});
        E.pb({u,v,w});
    }

    a.resize(n+1);

    for(int i=0; i<s; i++){
        int x;
        cin >> x;
        a[x]=1;
    }
    tin.resize(n+1);
    tout.resize(n+1);
    dep.resize(n+1);
    down.resize(n+1,1e18);
    dist.resize(n+1);
    up.resize(n+1,vi(lg,-1));
    mn.resize(n+1,vl(lg,1e18));

    dfs(e,-1);

    for(int j=1; j<lg; j++)
        for(int i=1; i<=n; i++){
            if(up[i][j-1]==-1)
                continue;
            up[i][j]=up[up[i][j-1]][j-1];
            mn[i][j]=min(mn[i][j-1],mn[up[i][j-1]][j-1]);
        }

    while(q--){
        int i,r;
        cin >> i >> r;
        int u=E[i-1][0],v=E[i-1][1];
        if(dep[u]<dep[v])
            swap(u,v);
        //u is lower

        if(!(tin[u]<=tin[r] && tout[r]<=tout[u])){
            cout << "escaped" << endl;
            continue;
        }
        if(s==n){
            cout << "0" << endl;
            continue;
        }
        ll ans=calc(r,u,v);
        if(ans==1e18)
            cout << "oo" << endl;
        else
            cout << ans << endl;
    }
}

Compilation message

valley.cpp: In function 'void usaco(std::string)':
valley.cpp:57:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |     freopen(FIN, "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~
valley.cpp:58:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |     freopen(FOUT, "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 460 KB Output is correct
2 Correct 13 ms 444 KB Output is correct
3 Correct 13 ms 464 KB Output is correct
4 Correct 13 ms 468 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 460 KB Output is correct
2 Correct 13 ms 444 KB Output is correct
3 Correct 13 ms 464 KB Output is correct
4 Correct 13 ms 468 KB Output is correct
5 Correct 2 ms 724 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 2 ms 852 KB Output is correct
8 Correct 2 ms 724 KB Output is correct
9 Correct 2 ms 724 KB Output is correct
10 Correct 2 ms 724 KB Output is correct
11 Correct 3 ms 724 KB Output is correct
12 Correct 3 ms 724 KB Output is correct
13 Correct 3 ms 852 KB Output is correct
14 Correct 2 ms 852 KB Output is correct

Subtask #3
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 286 ms 52612 KB Output is correct
2 Correct 301 ms 52352 KB Output is correct
3 Correct 313 ms 52416 KB Output is correct
4 Correct 341 ms 54516 KB Output is correct
5 Correct 349 ms 54644 KB Output is correct
6 Correct 356 ms 57152 KB Output is correct

Subtask #4
41.0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 460 KB Output is correct
2 Correct 13 ms 444 KB Output is correct
3 Correct 13 ms 464 KB Output is correct
4 Correct 13 ms 468 KB Output is correct
5 Correct 2 ms 724 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 2 ms 852 KB Output is correct
8 Correct 2 ms 724 KB Output is correct
9 Correct 2 ms 724 KB Output is correct
10 Correct 2 ms 724 KB Output is correct
11 Correct 3 ms 724 KB Output is correct
12 Correct 3 ms 724 KB Output is correct
13 Correct 3 ms 852 KB Output is correct
14 Correct 2 ms 852 KB Output is correct
15 Correct 286 ms 52612 KB Output is correct
16 Correct 301 ms 52352 KB Output is correct
17 Correct 313 ms 52416 KB Output is correct
18 Correct 341 ms 54516 KB Output is correct
19 Correct 349 ms 54644 KB Output is correct
20 Correct 356 ms 57152 KB Output is correct
21 Correct 301 ms 51992 KB Output is correct
22 Correct 317 ms 51836 KB Output is correct
23 Correct 322 ms 51796 KB Output is correct
24 Correct 391 ms 54244 KB Output is correct
25 Correct 453 ms 57668 KB Output is correct
26 Correct 288 ms 51980 KB Output is correct
27 Correct 345 ms 51808 KB Output is correct
28 Correct 342 ms 51824 KB Output is correct
29 Correct 375 ms 53464 KB Output is correct
30 Correct 403 ms 55228 KB Output is correct
31 Correct 288 ms 52152 KB Output is correct
32 Correct 314 ms 51972 KB Output is correct
33 Correct 323 ms 51952 KB Output is correct
34 Correct 376 ms 54164 KB Output is correct
35 Correct 384 ms 57520 KB Output is correct
36 Correct 374 ms 54384 KB Output is correct