Submission #694276

#	Time	Username	Problem	Language	Result	Execution time	Memory
694276		vjudge1	Valley (BOI19_valley)	C++17	9 / 100	68 ms	6336 KiB

valley

#pragma gcc optimize("Ofast")
#pragma GCC optimization("Ofast")
#pragma optimize(Ofast)
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")

/**
 *    author:  tpa1410 - futorankusu
 *    rose, hanni, minji     
**/

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
#define rose() ios_base::sync_with_stdio(NULL); cin.tie(nullptr); cout.tie(nullptr);
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define gcd __gcd
#define getl(s) getline(cin, s);
#define setpre(x) fixed << setprecision(x)
#define mset(a) memset(a, 0, sizeof(a))
#define endl '\n'

const ll hanni = 2e5+5, minji = 101;
const ll INF = ll(2e18) + 666;

ll dist[minji];
bool check_shop[minji];
int n,e;
vector<pair<int,int> > adj;
vector<ll> weights;

void solve(){
    int s,q;
    cin >> n >> s >> q >> e;
    for(int i = 0; i < n-1; ++i){
        int a,b,w;
        cin >> a >> b >> w;
        adj.pb({a,b});
        weights.pb(w);
    }
    for(int i = 0; i < s; ++i){
        int u;
        cin >> u;
        check_shop[u] = true;
    }
    for(int i = 0; i < q; ++i){
        int id,u;
        cin >> id >> u;
        --id;
        memset(dist,0x3f,sizeof dist);
        dist[u] = 0;
        while(1){
            bool changes = false;
            for(int i = 0; i < n-1; ++i){
                if(i == id) ++i;
                int x = adj[i].first, y = adj[i].second;
                if(dist[x] > dist[y] + weights[i]){
                    dist[x] = dist[y]+weights[i];
                    changes = true;
                }
                if(dist[y] > dist[x] + weights[i]){
                    dist[y] = dist[x]+weights[i];
                    changes = true;
                }
            }
            if(!changes)
                break;
        }
        //cout << dist[e] << '\n';
        if(dist[e] < dist[0])
            cout<<"escaped"<<endl;
        else{
            ll dist_toshop = dist[0];
            for(int i = 1; i <= n; ++i)
                if(check_shop[i])
                    dist_toshop = min(dist_toshop,dist[i]);
            if(dist_toshop < dist[0])
                cout<<dist_toshop<<endl;
            else
                cout<<"oo"<<endl;
        }
    }
}
int main(){
    rose();
    solve();
}

Compilation message (stderr)

valley.cpp:1: warning: ignoring '#pragma gcc optimize' [-Wunknown-pragmas]
    1 | #pragma gcc optimize("Ofast")
      | 
valley.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    2 | #pragma GCC optimization("Ofast")
      | 
valley.cpp:3: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    3 | #pragma optimize(Ofast)
      |

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