oj.uz

Submission #748796

# Submission time Handle Problem Language Result Execution time Memory
748796 2023-05-27T02:57:37 Z amogususus Evacuation plan (IZhO18_plan) C++17
23 / 100
 610 ms 91548 KB 
#pragma GCC optimize("Ofast,unroll-loops,inline")
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define pb push_back
#define prec fixed<<setprecision
#define endl '\n'
#define all(x) x.begin(),x.end()
#define pll pair<ll,ll>
#define open(name) if(fopen(name".inp", "r")){freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
#define fout(name) freopen(name".out", "w", stdout);
using namespace std;
using namespace std;
const int maxN=1e5+2;
ll n,m,k,q,dist[maxN],lab[maxN];
vector<pll> adj[maxN];
bool cs(pll x,pll y){return x.second<y.second;}
ll fset(ll x){return lab[x]<0?x:lab[x]=fset(lab[x]);}
void uset(ll x,ll y){
    if((x=fset(x))!=(y=fset(y))){
        if(lab[x]>lab[y])swap(x,y);
        lab[x]+=lab[y];
        lab[y]=x;
    }
}

priority_queue<pll,vector<pll>,greater<pll>> pq;
void dijkstra(){
    while (!pq.empty()) {
        ll u = pq.top().second;pq.pop();
        for (auto x : adj[u]) {
            ll v = x.first,w = x.second;
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
}
vector<pair<ll,pll>> edg;
vector<ll> g[maxN];
ll d[maxN],tin[maxN],tout[maxN],up[maxN][20],mx[maxN][20],timer=0;
void dfs(ll u=1,ll p=1){
    tin[u] = ++timer;
    up[u][0] = p;
    mx[u][0] = dist[u];
    for (int i = 1; i < 20; ++i)
        up[u][i] = up[up[u][i-1]][i-1],
        mx[u][i] = min(mx[u][i-1],mx[up[u][i-1]][i-1]);
    for(auto v:g[u])
        if(v!=p)dfs(v,u);
    tout[u] = ++timer;
}
bool is_ancestor(int u, int v){return tin[u] <= tin[v] && tout[u] >= tout[v];}
int lca(int u, int v){
    if (is_ancestor(u, v))return u;
    if (is_ancestor(v, u))return v;
    for (int i = 19; i >= 0; --i)
        if (!is_ancestor(up[u][i], v))
            u = up[u][i];
    return up[u][0];
}
ll res[maxN];
ll getmax(ll u,ll v){
    ll r=1e18;
    for (int i = 19; i >= 0; --i)
        if (!is_ancestor(up[u][i], v))
            r=min(r,mx[u][i]),
            u = up[u][i];
    return min(r,mx[u][0]);
}
void Enter(){
    memset(lab,-1,sizeof lab);
    cin>>n>>m;
    for(int i=1;i<=n;i++)dist[i]=1e15;
    for(int i=1;i<=m;i++){
        ll u,v,w;
        cin>>u>>v>>w;
        adj[u].pb({v,w});
        adj[v].pb({u,w});
        edg.pb({-69,{u,v}});
    }
    for(int i=1;i<=n;i++)sort(all(adj[i]),cs);
    cin>>k;
    for(int i=1;i<=k;i++){
        ll u;
        cin>>u;
        dist[u]=0;
        pq.push({0,u});
    }
    ///
    dijkstra();
    for(int i=0;i<edg.size();i++)edg[i].first=min(dist[edg[i].second.first],dist[edg[i].second.second]);
    sort(all(edg),greater<pair<ll,pll>>());
    for(auto x:edg){
        ll u=x.second.first,v=x.second.second;
        if(fset(u)!=fset(v))uset(u,v),g[u].pb(v),g[v].pb(u);
    }
    dfs();
    cin>>q;
    for(int i=1;i<=q;i++){
        ll u,v;
        cin>>u>>v;
        cout<<min(getmax(u,lca(u,v)),getmax(v,lca(u,v)))<<endl;
    }
}
//amogus
signed main(){
    open("EVACUATION");
    cin.tie(nullptr);ios_base::sync_with_stdio(NULL);
    ll t=1;
    //cin>>t;
    while(t--)
    Enter();
}

Compilation message

plan.cpp: In function 'void Enter()':
plan.cpp:93:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |     for(int i=0;i<edg.size();i++)edg[i].first=min(dist[edg[i].second.first],dist[edg[i].second.second]);
      |                 ~^~~~~~~~~~~
plan.cpp: In function 'int main()':
plan.cpp:10:54: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 | #define open(name) if(fopen(name".inp", "r")){freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
      |                                               ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
plan.cpp:109:5: note: in expansion of macro 'open'
  109 |     open("EVACUATION");
      |     ^~~~
plan.cpp:10:87: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 | #define open(name) if(fopen(name".inp", "r")){freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
      |                                                                                ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
plan.cpp:109:5: note: in expansion of macro 'open'
  109 |     open("EVACUATION");
      |     ^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5844 KB Output is correct
2 Correct 5 ms 6308 KB Output is correct
3 Correct 4 ms 6344 KB Output is correct
4 Correct 3 ms 5820 KB Output is correct
5 Correct 5 ms 6228 KB Output is correct
6 Correct 4 ms 6344 KB Output is correct
7 Correct 4 ms 5844 KB Output is correct
8 Correct 3 ms 5844 KB Output is correct
9 Correct 5 ms 6228 KB Output is correct
10 Correct 4 ms 6344 KB Output is correct
11 Correct 4 ms 6228 KB Output is correct
12 Correct 5 ms 6228 KB Output is correct
13 Correct 4 ms 6220 KB Output is correct
14 Correct 4 ms 6216 KB Output is correct
15 Correct 5 ms 6228 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5844 KB Output is correct
2 Correct 5 ms 6308 KB Output is correct
3 Correct 4 ms 6344 KB Output is correct
4 Correct 3 ms 5820 KB Output is correct
5 Correct 5 ms 6228 KB Output is correct
6 Correct 4 ms 6344 KB Output is correct
7 Correct 4 ms 5844 KB Output is correct
8 Correct 3 ms 5844 KB Output is correct
9 Correct 5 ms 6228 KB Output is correct
10 Correct 4 ms 6344 KB Output is correct
11 Correct 4 ms 6228 KB Output is correct
12 Correct 5 ms 6228 KB Output is correct
13 Correct 4 ms 6220 KB Output is correct
14 Correct 4 ms 6216 KB Output is correct
15 Correct 5 ms 6228 KB Output is correct
16 Correct 225 ms 45752 KB Output is correct
17 Correct 579 ms 91040 KB Output is correct
18 Correct 38 ms 14336 KB Output is correct
19 Correct 170 ms 55244 KB Output is correct
20 Correct 610 ms 91148 KB Output is correct
21 Correct 309 ms 63496 KB Output is correct
22 Correct 203 ms 57960 KB Output is correct
23 Correct 556 ms 91100 KB Output is correct
24 Correct 574 ms 91024 KB Output is correct
25 Correct 583 ms 91076 KB Output is correct
26 Correct 153 ms 55040 KB Output is correct
27 Correct 144 ms 55132 KB Output is correct
28 Correct 151 ms 55144 KB Output is correct
29 Correct 146 ms 55212 KB Output is correct
30 Correct 160 ms 55252 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5824 KB Output is correct
2 Incorrect 3 ms 5840 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 257 ms 61372 KB Output is correct
2 Correct 511 ms 89528 KB Output is correct
3 Correct 496 ms 89320 KB Output is correct
4 Correct 151 ms 54136 KB Output is correct
5 Correct 523 ms 89328 KB Output is correct
6 Correct 536 ms 89452 KB Output is correct
7 Correct 494 ms 89344 KB Output is correct
8 Correct 530 ms 89300 KB Output is correct
9 Correct 548 ms 89356 KB Output is correct
10 Correct 513 ms 89428 KB Output is correct
11 Correct 502 ms 89344 KB Output is correct
12 Correct 501 ms 89324 KB Output is correct
13 Correct 500 ms 89428 KB Output is correct
14 Correct 488 ms 89392 KB Output is correct
15 Correct 495 ms 91548 KB Output is correct
16 Correct 499 ms 89352 KB Output is correct
17 Correct 501 ms 89332 KB Output is correct
18 Correct 502 ms 89436 KB Output is correct
19 Correct 129 ms 55668 KB Output is correct
20 Correct 501 ms 89464 KB Output is correct
21 Correct 478 ms 89308 KB Output is correct
22 Incorrect 105 ms 53560 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5844 KB Output is correct
2 Correct 5 ms 6308 KB Output is correct
3 Correct 4 ms 6344 KB Output is correct
4 Correct 3 ms 5820 KB Output is correct
5 Correct 5 ms 6228 KB Output is correct
6 Correct 4 ms 6344 KB Output is correct
7 Correct 4 ms 5844 KB Output is correct
8 Correct 3 ms 5844 KB Output is correct
9 Correct 5 ms 6228 KB Output is correct
10 Correct 4 ms 6344 KB Output is correct
11 Correct 4 ms 6228 KB Output is correct
12 Correct 5 ms 6228 KB Output is correct
13 Correct 4 ms 6220 KB Output is correct
14 Correct 4 ms 6216 KB Output is correct
15 Correct 5 ms 6228 KB Output is correct
16 Correct 225 ms 45752 KB Output is correct
17 Correct 579 ms 91040 KB Output is correct
18 Correct 38 ms 14336 KB Output is correct
19 Correct 170 ms 55244 KB Output is correct
20 Correct 610 ms 91148 KB Output is correct
21 Correct 309 ms 63496 KB Output is correct
22 Correct 203 ms 57960 KB Output is correct
23 Correct 556 ms 91100 KB Output is correct
24 Correct 574 ms 91024 KB Output is correct
25 Correct 583 ms 91076 KB Output is correct
26 Correct 153 ms 55040 KB Output is correct
27 Correct 144 ms 55132 KB Output is correct
28 Correct 151 ms 55144 KB Output is correct
29 Correct 146 ms 55212 KB Output is correct
30 Correct 160 ms 55252 KB Output is correct
31 Correct 4 ms 5824 KB Output is correct
32 Incorrect 3 ms 5840 KB Output isn't correct
33 Halted 0 ms 0 KB -