oj.uz

Submission #945618

# Submission time Handle Problem Language Result Execution time Memory
945618 2024-03-14T05:37:30 Z yeediot Valley (BOI19_valley) C++14
100 / 100
 134 ms 57600 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define pb push_back
#define sz(x) (int)(x.size())
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define vi vector<int>
#define vp vector<pii>
#define vvi vector<vi>
#define ykh mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count())
#define __lg(x) 63-__builtin_clzll(x)
#define pow2(x) (1LL<<x)
void __print(int x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef local
void setio(){freopen("/Users/iantsai/Library/Mobile Documents/com~apple~CloudDocs/cpp/Empty.md","r",stdin);}
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
void setio(){}
#define debug(x...)
#endif
void setIO(string s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}
struct line{
    int a,b;
    int operator()(const int x)const{
        return a*x+b;
    }
};
bool check(line l1,line l2,line l3){
    return (l3.b-l2.b)*(l1.a-l2.a)<=(l2.b-l1.b)*(l2.a-l3.a);
}
const int mxn=1e5+5;
vector<pii>adj[mxn];
bool isshop[mxn];
int dep[mxn],d[mxn];
int in[mxn],out[mxn];
int timer;
vector<tuple<int,int,int>>edge;
int jump[20][mxn],mn[20][mxn];
int ord[mxn];
int dp[mxn];
int pre[mxn];
void dfs(int v,int pa){
    in[v]=++timer;
    ord[timer]=v;
    jump[0][v]=pa;
    if(isshop[v])dp[v]=0;
    else dp[v]=1e18;
    for(auto [u,pp]:adj[v]){
        if(u==pa)continue;
        dep[u]=dep[v]+pp;
        d[u]=d[v]+1;
        dfs(u,v);
        dp[v]=min(dp[v],dp[u]+pp);
    }
    out[v]=timer;
}
int lca(int v,int u){
    if(dep[v]<dep[u])swap(v,u);
    int dif=d[v]-d[u];
    for(int i=0;i<20;i++){
        if(dif>>i&1){
            v=jump[i][v];
        }
    }
    if(v==u)return v;
    for(int i=19;i>=0;i--){
        if(jump[i][v]!=jump[i][u]){
            v=jump[i][v];
            u=jump[i][u];
        }
    }
    return jump[0][v];
}
int ans[mxn];
void calc(int v,int pa){
    mn[0][v]=dp[jump[0][v]]-dep[jump[0][v]];
    for(auto [u,dd]:adj[v]){
        if(u==pa)continue;
        calc(u,v);
    }
}
signed main(){
    setio();
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n,s,q,e;
    cin>>n>>s>>q>>e;
    for(int i=1;i<n;i++){
        int a,b,c;
        cin>>a>>b>>c;
        adj[a].pb({b,c});
        adj[b].pb({a,c});
        edge.pb({a,b,c});
    }
    for(int i=1;i<=s;i++){
        int x;
        cin>>x;
        isshop[x]=1;
    }
    dfs(e,e);
    for(int i=1;i<20;i++){
        for(int j=1;j<=n;j++){
            jump[i][j]=jump[i-1][jump[i-1][j]];
        }
    }
    calc(e,e);
    for(int i=1;i<20;i++){
        for(int j=1;j<=n;j++){
            mn[i][j]=min(mn[i-1][j],mn[i-1][jump[i-1][j]]);
        }
    }
    while(q--){
        int id,v;
        cin>>id>>v;
        id--;
        auto [x,y,l]=edge[id];
        if(d[x]<d[y])swap(x,y);
        //debug(x);
        if(in[x]<=in[v] and in[v]<=out[x]){
            int an=dp[v];
            int cur=v;
            if(cur!=x){
                for(int i=19;i>=0;i--){
                    if(dep[jump[i][cur]]>dep[x]){
                        an=min(an,mn[i][cur]+dep[v]);
                        cur=jump[i][cur];
                        debug(cur);
                    }
                }
                an=min(an,mn[0][cur]+dep[v]);
            }
            if(an>=1e18){
                cout<<"oo\n";
            }
            else{
                cout<<an<<'\n';
            }
        }  
        else{
            cout<<"escaped\n";
        }
    }
}
 /*
 input:
 
 */

Compilation message

valley.cpp: In function 'void dfs(long long int, long long int)':
valley.cpp:71:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   71 |     for(auto [u,pp]:adj[v]){
      |              ^
valley.cpp: In function 'void calc(long long int, long long int)':
valley.cpp:100:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  100 |     for(auto [u,dd]:adj[v]){
      |              ^
valley.cpp: In function 'int main()':
valley.cpp:139:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  139 |         auto [x,y,l]=edge[id];
      |              ^
valley.cpp: In function 'void setIO(std::string)':
valley.cpp:42:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |     freopen((s + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:43:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |     freopen((s + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 40280 KB Output is correct
2 Correct 7 ms 40280 KB Output is correct
3 Correct 7 ms 40572 KB Output is correct
4 Correct 7 ms 40284 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 40280 KB Output is correct
2 Correct 7 ms 40280 KB Output is correct
3 Correct 7 ms 40572 KB Output is correct
4 Correct 7 ms 40284 KB Output is correct
5 Correct 5 ms 40284 KB Output is correct
6 Correct 5 ms 40284 KB Output is correct
7 Correct 6 ms 40420 KB Output is correct
8 Correct 5 ms 40284 KB Output is correct
9 Correct 6 ms 40344 KB Output is correct
10 Correct 5 ms 40284 KB Output is correct
11 Correct 6 ms 40284 KB Output is correct
12 Correct 6 ms 40336 KB Output is correct
13 Correct 6 ms 40280 KB Output is correct
14 Correct 6 ms 40284 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 48956 KB Output is correct
2 Correct 98 ms 48124 KB Output is correct
3 Correct 109 ms 48712 KB Output is correct
4 Correct 125 ms 50172 KB Output is correct
5 Correct 96 ms 50408 KB Output is correct
6 Correct 134 ms 52728 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 40280 KB Output is correct
2 Correct 7 ms 40280 KB Output is correct
3 Correct 7 ms 40572 KB Output is correct
4 Correct 7 ms 40284 KB Output is correct
5 Correct 5 ms 40284 KB Output is correct
6 Correct 5 ms 40284 KB Output is correct
7 Correct 6 ms 40420 KB Output is correct
8 Correct 5 ms 40284 KB Output is correct
9 Correct 6 ms 40344 KB Output is correct
10 Correct 5 ms 40284 KB Output is correct
11 Correct 6 ms 40284 KB Output is correct
12 Correct 6 ms 40336 KB Output is correct
13 Correct 6 ms 40280 KB Output is correct
14 Correct 6 ms 40284 KB Output is correct
15 Correct 84 ms 48956 KB Output is correct
16 Correct 98 ms 48124 KB Output is correct
17 Correct 109 ms 48712 KB Output is correct
18 Correct 125 ms 50172 KB Output is correct
19 Correct 96 ms 50408 KB Output is correct
20 Correct 134 ms 52728 KB Output is correct
21 Correct 80 ms 52256 KB Output is correct
22 Correct 95 ms 51576 KB Output is correct
23 Correct 105 ms 52476 KB Output is correct
24 Correct 122 ms 53764 KB Output is correct
25 Correct 119 ms 57600 KB Output is correct
26 Correct 80 ms 51708 KB Output is correct
27 Correct 91 ms 51560 KB Output is correct
28 Correct 102 ms 51640 KB Output is correct
29 Correct 124 ms 53088 KB Output is correct
30 Correct 122 ms 54776 KB Output is correct
31 Correct 83 ms 52028 KB Output is correct
32 Correct 95 ms 52196 KB Output is correct
33 Correct 102 ms 51892 KB Output is correct
34 Correct 126 ms 54016 KB Output is correct
35 Correct 124 ms 57344 KB Output is correct
36 Correct 106 ms 53764 KB Output is correct