oj.uz

답안 #890622

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
890622 2023-12-21T16:22:33 Z cpptowin Valley (BOI19_valley) C++17
100 / 100
 149 ms 84820 KB 
#include<bits/stdc++.h>
#define fo(i,d,c) for(int i=d;i<=c;i++)
#define fod(i,c,d) for(int i=c;i>=d;i--)
#define maxn 1000010
#define N 1010
#define fi first
#define se second
#define pb emplace_back
#define en cout<<"\n";
#define int long long
#define inf 1000000000
#define pii pair<int,int>
#define vii vector<pii>
#define lb(x) x&-x
#define bit(i,j) ((i>>j)&1)
#define offbit(i,j) (i^(1<<j))
#define onbit(i,j) (i|(1<<j))
#define vi vector<int>
template <typename T1, typename T2> bool minimize(T1 &a, T2 b){if (a > b) {a = b; return true;} return false;}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b){if (a < b) {a = b; return true;} return false;}
using namespace std;
int par[maxn][20],minn[maxn][20];
int magic[maxn];
vii ke[maxn];
int n;
int d[maxn];
pii edge[maxn];
int S,E,Q;
bool shop[maxn];
int h[maxn];
void calcmagic(int u,int parent)
{
    if(shop[u]) magic[u] = d[u];
    for(auto [v,w] : ke[u])
    {
        if(v == parent) continue;
        par[v][0] = u;
        h[v] = h[u] + 1;
        d[v] = d[u] + w;
        calcmagic(v,u);
        magic[u] = min(magic[u],magic[v]);
    }
}
int lca(int u, int v)
{
    if (h[u] < h[v])
        swap(u, v);
    int del = h[u] - h[v];
    fod(i, 19, 0) if (bit(del, i)) u = par[u][i];
    if (u == v)
        return u;
    fod(i, 19, 0) if (par[u][i] != par[v][i]) u = par[u][i], v = par[v][i];
    return par[u][0];
}
main()
{
    #define name "TASK"
    if(fopen(name".inp","r"))
    {
       freopen(name".inp","r",stdin);
       freopen(name".out","w",stdout);
    }
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    cin >> n >> S >> Q >> E;
    fo(i,1,n - 1)
    {
        int u,v,w;
        cin >> u >> v >> w;
        ke[u].pb(v,w);
        ke[v].pb(u,w);
        edge[i] = {u,v};
    }
    fo(i,1,S)
    {
        int x;
        cin >> x;
        shop[x] = 1;
    }
    fo(i,1,n) magic[i] = 1e18;
    calcmagic(E,E);
//    fo(i,1,n) cout << magic[i] << ' ';en;
    fo(i,1,n) if(magic[i] < 1e18) magic[i] = magic[i] - 2 * d[i];
//    fo(i,1,n) cout << magic[i] << ' ';en;
    fo(j,1,19) fo(i,1,n) par[i][j] = par[par[i][j - 1]][j - 1];
    fo(i,1,n) minn[i][0] = magic[par[i][0]];
    fo(j,1,19) fo(i,1,n) minn[i][j] = min(minn[i][j - 1],minn[par[i][j - 1]][j - 1]);
//    cout << lca()
    while(Q--)
    {
        int id,r;
        cin >> id >> r;
        if(lca(edge[id].se,r) != edge[id].se or lca(edge[id].fi,r) != edge[id].fi) cout << "escaped \n";
        else
        {
            int val = d[r];
            int ans = 1e18;
            int del = h[r] - max(h[edge[id].fi],h[edge[id].se]);
            ans = min(ans,magic[r]);
            fod(i,19,0) if(bit(del,i)) ans = min(ans,minn[r][i]),r = par[r][i];
            if(ans == 1e18) cout << "oo";
            else cout << val + ans;
            en;
        }
    }
}

Compilation message

valley.cpp:55:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   55 | main()
      | ^~~~
valley.cpp: In function 'int main()':
valley.cpp:60:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |        freopen(name".inp","r",stdin);
      |        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
valley.cpp:61:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |        freopen(name".out","w",stdout);
      |        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 35420 KB Output is correct
2 Correct 9 ms 35420 KB Output is correct
3 Correct 9 ms 35348 KB Output is correct
4 Correct 9 ms 35420 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 35420 KB Output is correct
2 Correct 9 ms 35420 KB Output is correct
3 Correct 9 ms 35348 KB Output is correct
4 Correct 9 ms 35420 KB Output is correct
5 Correct 7 ms 35420 KB Output is correct
6 Correct 7 ms 35420 KB Output is correct
7 Correct 7 ms 35416 KB Output is correct
8 Correct 7 ms 35292 KB Output is correct
9 Correct 7 ms 35420 KB Output is correct
10 Correct 7 ms 35420 KB Output is correct
11 Correct 8 ms 35420 KB Output is correct
12 Correct 7 ms 35420 KB Output is correct
13 Correct 8 ms 35416 KB Output is correct
14 Correct 7 ms 35420 KB Output is correct

Subtask #3
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 113 ms 76372 KB Output is correct
2 Correct 123 ms 78672 KB Output is correct
3 Correct 134 ms 80464 KB Output is correct
4 Correct 143 ms 80980 KB Output is correct
5 Correct 128 ms 80980 KB Output is correct
6 Correct 149 ms 83484 KB Output is correct

Subtask #4
41.0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 35420 KB Output is correct
2 Correct 9 ms 35420 KB Output is correct
3 Correct 9 ms 35348 KB Output is correct
4 Correct 9 ms 35420 KB Output is correct
5 Correct 7 ms 35420 KB Output is correct
6 Correct 7 ms 35420 KB Output is correct
7 Correct 7 ms 35416 KB Output is correct
8 Correct 7 ms 35292 KB Output is correct
9 Correct 7 ms 35420 KB Output is correct
10 Correct 7 ms 35420 KB Output is correct
11 Correct 8 ms 35420 KB Output is correct
12 Correct 7 ms 35420 KB Output is correct
13 Correct 8 ms 35416 KB Output is correct
14 Correct 7 ms 35420 KB Output is correct
15 Correct 113 ms 76372 KB Output is correct
16 Correct 123 ms 78672 KB Output is correct
17 Correct 134 ms 80464 KB Output is correct
18 Correct 143 ms 80980 KB Output is correct
19 Correct 128 ms 80980 KB Output is correct
20 Correct 149 ms 83484 KB Output is correct
21 Correct 106 ms 78440 KB Output is correct
22 Correct 125 ms 78216 KB Output is correct
23 Correct 122 ms 78508 KB Output is correct
24 Correct 143 ms 80720 KB Output is correct
25 Correct 138 ms 83680 KB Output is correct
26 Correct 104 ms 78420 KB Output is correct
27 Correct 118 ms 78348 KB Output is correct
28 Correct 123 ms 78372 KB Output is correct
29 Correct 143 ms 79952 KB Output is correct
30 Correct 137 ms 81916 KB Output is correct
31 Correct 108 ms 78404 KB Output is correct
32 Correct 116 ms 78452 KB Output is correct
33 Correct 122 ms 78676 KB Output is correct
34 Correct 141 ms 80516 KB Output is correct
35 Correct 138 ms 84820 KB Output is correct
36 Correct 131 ms 80616 KB Output is correct