제출 #441438

#제출 시각아이디문제언어결과실행 시간메모리
441438cpp219Valley (BOI19_valley)C++14
0 / 100
4 ms1232 KiB
#pragma GCC optimization O2 #pragma GCC optimization "unroll-loop" #pragma target ("avx2") #include <bits/stdc++.h> #define ll long long #define ld long double #define fs first #define sc second using namespace std; typedef pair<ll,ll> LL; const ll N = 1e3 + 9; const ll Log2 = 20; const ll inf = 1e12 + 7; const ll lim = 1e9 + 7; vector<LL> g[N]; LL edge[N]; ll n,S,Q,E,x,y,w,par[N][20],d[N],dp[N][20],val[N],dep[N]; ll nTime,L[N],R[N]; void DFS(ll u,ll p){ L[u] = R[u] = nTime; nTime++; for (auto i : g[u]){ ll v = i.fs,L = i.sc; if (v == p) continue; d[v] = d[u] + 1; dep[v] = dep[u] + L; par[v][0] = u; DFS(v,u); R[u] = max(R[u],R[v]); val[u] = min(val[u],L + val[v]); } dp[u][0] = val[u] - dep[u]; } void reDFS(ll u,ll p){ //cout<<u<<" "<<p<<"\n"; //cout<<g[u][0].fs; exit(0); for (ll i = 1;i < Log2;i++) if ((1 << i) <= d[u]) par[u][i] = par[par[u][i - 1]][i - 1], dp[u][i] = min(dp[u][i - 1],dp[par[u][i - 1]][i - 1]); for (auto i : g[u]) if (i.fs != p){ dp[i.fs][0] = min(dp[i.fs][0],dp[u][0]); reDFS(i.fs,u); } } ll Jump(ll node,ll step){ ll res = inf; for (ll i = Log2 - 1;i >= 0;i--){ if ((1 << i) > step) continue; //cout<<dp[5][1]<<"x"; exit(0); res = min(res,dp[node][i]); node = par[node][i]; step -= (1 << i); } return res; } int main(){ ios_base::sync_with_stdio(NULL); cin.tie(0); cout.tie(0); #define task "tst" if (fopen(task".INP","r")){ freopen(task".INP","r",stdin); //freopen(task".OUT","w",stdout); } cin>>n>>S>>Q>>E; fill(val,val + n + 1,inf); for (ll i = 1;i < n;i++){ cin>>x>>y>>w; edge[i] = {x,y}; g[x].push_back({y,w}); g[y].push_back({x,w}); } for (ll i = 1;i <= S;i++) cin>>x,val[x] = 0; DFS(E,0); reDFS(E,0); //return 0; while(Q--){ cin>>x>>y; if (d[edge[x].fs] < d[edge[x].sc]) swap(edge[x].fs,edge[x].sc); ll l = edge[x].fs; if (L[l] <= L[y] && R[y] <= R[l]){ ll kq = Jump(y,d[y] - d[l]); //cout<<kq; return 0; if (kq > lim) cout<<"oo"; else cout<<kq + dep[y]; } else cout<<"escaped"; cout<<"\n"; } }

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

valley.cpp:1: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    1 | #pragma GCC optimization O2
      | 
valley.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    2 | #pragma GCC optimization "unroll-loop"
      | 
valley.cpp:3: warning: ignoring '#pragma target ' [-Wunknown-pragmas]
    3 | #pragma target ("avx2")
      | 
valley.cpp: In function 'int main()':
valley.cpp:61:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |         freopen(task".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...