oj.uz

Submission #644232

# Submission time Handle Problem Language Result Execution time Memory
644232 2022-09-24T06:16:23 Z guagua0407 Valley (BOI19_valley) C++17
100 / 100
 169 ms 50740 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

void setIO(string s) {
	freopen((s + ".in").c_str(), "r", stdin);
	freopen((s + ".out").c_str(), "w", stdout);
}

const int mxn=1e5+5;
vector<pair<int,int>> adj[mxn];
pair<int,int> edgeid[mxn];
bool isshop[mxn]={false};
ll depth[mxn]={0},length[mxn]={0};
ll magic[mxn]={(ll)1e18};
ll jumping[20][mxn],jumpingans[20][mxn];
int st[mxn],en[mxn];
int parent[mxn];
int timer=0;

ll query(int top,int node){
    int x=node;
    int pathlength=depth[node]-depth[top];
    ll ans=magic[node];
    for(int i=0;i<20;i++){
        if(pathlength & (1<<i)){
            ans=min(ans,jumpingans[i][node]);
            node=jumping[i][node];
        }
    }
    return ans+length[x];
}

void dfs(int v,int p){
    st[v]=timer;
    timer++;
    parent[v]=p;
    for(auto u:adj[v]){
        if(u.f==p) continue;
        depth[u.f]=depth[v]+1;
        //cout<<v<<' '<<u.f<<' '<<u.s<<'\n';
        length[u.f]=length[v]+u.s;
        dfs(u.f,v);
    }
    en[v]=timer;
    timer++;
}

void dfs2(int v,int p){
    if(isshop[v]) magic[v]=length[v];
    else magic[v]=(ll)1e18;
    for(auto u:adj[v]){
        if(u.f==p) continue;
        dfs2(u.f,v);
        magic[v]=min(magic[v],magic[u.f]);
    }
}

int main() {_
	//setIO("wayne");
    int n,s,q,e;
    cin>>n>>s>>q>>e;
    for(int i=1;i<=n-1;i++){
        int a,b,w;
        cin>>a>>b>>w;
        adj[a].push_back({b,w});
        adj[b].push_back({a,w});
        edgeid[i]={a,b};
    }
    for(int i=0;i<s;i++){
        int x;
        cin>>x;
        isshop[x]=true;
    }
    dfs(e,0);
    dfs2(e,0);
    for(int i=1;i<=n;i++){
        magic[i]-=2*length[i];
    }
    for(int i=1;i<=n;i++){
        jumping[0][i]=parent[i];
        jumpingans[0][i]=magic[parent[i]];
    }
    for(int i=1;i<20;i++){
        for(int j=1;j<=n;j++){
            jumping[i][j]=jumping[i-1][jumping[i-1][j]];
            jumpingans[i][j]=min(jumpingans[i-1][j],jumpingans[i-1][jumping[i-1][j]]);
        }
    }
    /*for(int i=1;i<=n;i++){
        cout<<length[i]<<' ';
    }
    cout<<'\n';
    for(int i=1;i<=n;i++){
        cout<<magic[i]<<' ';
    }
    cout<<'\n';*/
    for(int i=0;i<q;i++){
        int edge,node;
        cin>>edge>>node;
        int top=(depth[edgeid[edge].f]>depth[edgeid[edge].s]?edgeid[edge].f:edgeid[edge].s);
        if(st[top]<=st[node] and en[node]<=en[top]){
            if(query(top,node)<=(ll)1e14) cout<<query(top,node)<<'\n';
            else cout<<"oo"<<'\n';
        }
        else{
            cout<<"escaped"<<'\n';
        }
    }
	return 0;
}
//maybe its multiset not set

Compilation message

valley.cpp: In function 'void setIO(std::string)':
valley.cpp:10:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |  freopen((s + ".in").c_str(), "r", stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:11:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |  freopen((s + ".out").c_str(), "w", stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3028 KB Output is correct
2 Correct 4 ms 3080 KB Output is correct
3 Correct 3 ms 3028 KB Output is correct
4 Correct 4 ms 3028 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3028 KB Output is correct
2 Correct 4 ms 3080 KB Output is correct
3 Correct 3 ms 3028 KB Output is correct
4 Correct 4 ms 3028 KB Output is correct
5 Correct 2 ms 3340 KB Output is correct
6 Correct 2 ms 3336 KB Output is correct
7 Correct 2 ms 3284 KB Output is correct
8 Correct 2 ms 3284 KB Output is correct
9 Correct 3 ms 3284 KB Output is correct
10 Correct 3 ms 3264 KB Output is correct
11 Correct 3 ms 3284 KB Output is correct
12 Correct 2 ms 3284 KB Output is correct
13 Correct 3 ms 3284 KB Output is correct
14 Correct 3 ms 3284 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 42956 KB Output is correct
2 Correct 111 ms 42572 KB Output is correct
3 Correct 126 ms 42524 KB Output is correct
4 Correct 149 ms 44404 KB Output is correct
5 Correct 141 ms 44448 KB Output is correct
6 Correct 153 ms 46240 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3028 KB Output is correct
2 Correct 4 ms 3080 KB Output is correct
3 Correct 3 ms 3028 KB Output is correct
4 Correct 4 ms 3028 KB Output is correct
5 Correct 2 ms 3340 KB Output is correct
6 Correct 2 ms 3336 KB Output is correct
7 Correct 2 ms 3284 KB Output is correct
8 Correct 2 ms 3284 KB Output is correct
9 Correct 3 ms 3284 KB Output is correct
10 Correct 3 ms 3264 KB Output is correct
11 Correct 3 ms 3284 KB Output is correct
12 Correct 2 ms 3284 KB Output is correct
13 Correct 3 ms 3284 KB Output is correct
14 Correct 3 ms 3284 KB Output is correct
15 Correct 109 ms 42956 KB Output is correct
16 Correct 111 ms 42572 KB Output is correct
17 Correct 126 ms 42524 KB Output is correct
18 Correct 149 ms 44404 KB Output is correct
19 Correct 141 ms 44448 KB Output is correct
20 Correct 153 ms 46240 KB Output is correct
21 Correct 95 ms 46076 KB Output is correct
22 Correct 106 ms 45728 KB Output is correct
23 Correct 127 ms 45720 KB Output is correct
24 Correct 126 ms 47808 KB Output is correct
25 Correct 169 ms 50740 KB Output is correct
26 Correct 97 ms 46160 KB Output is correct
27 Correct 113 ms 45888 KB Output is correct
28 Correct 118 ms 45816 KB Output is correct
29 Correct 156 ms 47192 KB Output is correct
30 Correct 151 ms 48612 KB Output is correct
31 Correct 117 ms 46216 KB Output is correct
32 Correct 111 ms 45928 KB Output is correct
33 Correct 126 ms 45952 KB Output is correct
34 Correct 135 ms 47752 KB Output is correct
35 Correct 135 ms 50516 KB Output is correct
36 Correct 126 ms 47988 KB Output is correct