oj.uz

Submission #544323

# Submission time Handle Problem Language Result Execution time Memory
544323 2022-04-01T16:48:24 Z somo Evacuation plan (IZhO18_plan) C++14
100 / 100
 570 ms 101684 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define ll long long
#define pb push_back
#define endl '\n'
#define pii pair<ll,ll>
#define F first
#define S second
#define double long double
#define all(x) (x).begin(),(x).end()

using namespace std;
using namespace __gnu_pbds;

typedef tree<ll , null_type , less_equal<ll> ,rb_tree_tag ,tree_order_statistics_node_update >ordered_set;

const int MOD = 1e9 + 7;
const int  N=5e5 + 7 ;
const ll INF= 1e18+10;

struct trp{ll F,S,T;};

ll po(ll x,ll y)
{
    ll ans = 1;
    while(y){
        if( y & 1 ) ans *=x;
        y /= 2;
        x *=x;
        x %= MOD;
        ans %= MOD;
    }
    return ans;
}

ll p[N];
ll vis[N];
ll ans[N];
bool is[N];
ll n , m , qu;
set<ll> dsu[N];
vector<pii>v[N];
vector<pii> que[N];

ll root(ll x)
{
    return p[x] == x ? x : p[x] = root(p[x]);
}

void mer(ll x,ll y,ll hehe)
{
    x = root(x);
    y = root(y);
    if(x == y) return;
    if(dsu[x].size() > dsu[y].size()) swap(x,y);
    for(auto i : dsu[x]){
        for(auto j : que[i]){
            if(dsu[y].find(j.F) != dsu[y].end()) ans[j.S] = hehe;
        }
    }
    for(auto i : dsu[x]) dsu[y].insert(i);
    p[x] = y;
}

bool cmp(pii a,pii b)
{
    return a.F < b.F;
}

void solve()
{
    cin >> n >> m ;
    for(ll i= 1; i <= m ; i ++){
        ll x,y,z;
        cin >> x >> y >> z;
        v[x].pb({y,z});
        v[y].pb({x,z});
    }
    for(ll i= 1; i <= n ; i ++){
        vis[i] = 1e17;
        p[i] = i;
        dsu[i].insert(i);
    }
    priority_queue<pii,vector<pii>,greater<pii>>q;
    ll k;
    cin >> k;
    while(k -- ){
        ll x;
        cin >> x;
        vis[x] = 0;
        q.push({0,x});
    }
    while(q.size()){
        pii x = q.top();
        q.pop();
        if(x.F != vis[x.S]) continue;
        for(auto i : v[x.S]){
            if(vis[i.F] > x.F + i.S){
                vis[i.F] = x.F + i.S;
                q.push({vis[i.F] , i.F});
            }
        }
    }
    vector<pii>vec;
    for(ll i= 1; i <= n ; i ++){
        vec.pb({vis[i] , i});
    }
    sort(all(vec) , cmp);
    cin >> qu;
    for(ll i= 1; i <= qu ; i ++){
        ll x,y;
        cin >> x >> y;
        que[x].pb({y,i});
        que[y].pb({x,i});
    }
    while(vec.size()){
        ll node = vec.back().S , hehe = vec.back().F;
        is[node] = 1;
        vec.pop_back();
        for(auto i : v[node]){
            if(!is[i.F]) continue;
            mer(node , i.F , hehe);
        }
    }
    for(ll i= 1; i <= qu ; i ++) cout << ans[i] << endl;
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	//freopen(".in" , "r" , stdin);freopen(".out" , "w" , stdout);
	int t = 1;
    //cin >> t;
	while(t--) {solve() ; }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 47296 KB Output is correct
2 Correct 24 ms 47580 KB Output is correct
3 Correct 23 ms 47496 KB Output is correct
4 Correct 22 ms 47316 KB Output is correct
5 Correct 23 ms 47548 KB Output is correct
6 Correct 23 ms 47576 KB Output is correct
7 Correct 24 ms 47256 KB Output is correct
8 Correct 24 ms 47308 KB Output is correct
9 Correct 23 ms 47560 KB Output is correct
10 Correct 23 ms 47564 KB Output is correct
11 Correct 26 ms 47568 KB Output is correct
12 Correct 24 ms 47544 KB Output is correct
13 Correct 23 ms 47528 KB Output is correct
14 Correct 25 ms 47580 KB Output is correct
15 Correct 22 ms 47600 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 47296 KB Output is correct
2 Correct 24 ms 47580 KB Output is correct
3 Correct 23 ms 47496 KB Output is correct
4 Correct 22 ms 47316 KB Output is correct
5 Correct 23 ms 47548 KB Output is correct
6 Correct 23 ms 47576 KB Output is correct
7 Correct 24 ms 47256 KB Output is correct
8 Correct 24 ms 47308 KB Output is correct
9 Correct 23 ms 47560 KB Output is correct
10 Correct 23 ms 47564 KB Output is correct
11 Correct 26 ms 47568 KB Output is correct
12 Correct 24 ms 47544 KB Output is correct
13 Correct 23 ms 47528 KB Output is correct
14 Correct 25 ms 47580 KB Output is correct
15 Correct 22 ms 47600 KB Output is correct
16 Correct 260 ms 74360 KB Output is correct
17 Correct 544 ms 101552 KB Output is correct
18 Correct 54 ms 52488 KB Output is correct
19 Correct 215 ms 74964 KB Output is correct
20 Correct 535 ms 101548 KB Output is correct
21 Correct 348 ms 83412 KB Output is correct
22 Correct 228 ms 74364 KB Output is correct
23 Correct 555 ms 101496 KB Output is correct
24 Correct 542 ms 101560 KB Output is correct
25 Correct 532 ms 101544 KB Output is correct
26 Correct 209 ms 74760 KB Output is correct
27 Correct 216 ms 74868 KB Output is correct
28 Correct 209 ms 74704 KB Output is correct
29 Correct 211 ms 74812 KB Output is correct
30 Correct 216 ms 74944 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 47260 KB Output is correct
2 Correct 22 ms 47284 KB Output is correct
3 Correct 23 ms 47208 KB Output is correct
4 Correct 22 ms 47316 KB Output is correct
5 Correct 24 ms 47284 KB Output is correct
6 Correct 23 ms 47304 KB Output is correct
7 Correct 25 ms 47420 KB Output is correct
8 Correct 22 ms 47288 KB Output is correct
9 Correct 24 ms 47308 KB Output is correct
10 Correct 23 ms 47324 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 266 ms 75988 KB Output is correct
2 Correct 441 ms 94036 KB Output is correct
3 Correct 439 ms 94088 KB Output is correct
4 Correct 159 ms 68556 KB Output is correct
5 Correct 423 ms 94012 KB Output is correct
6 Correct 422 ms 94188 KB Output is correct
7 Correct 429 ms 94080 KB Output is correct
8 Correct 445 ms 93964 KB Output is correct
9 Correct 427 ms 94108 KB Output is correct
10 Correct 425 ms 94072 KB Output is correct
11 Correct 421 ms 94036 KB Output is correct
12 Correct 431 ms 94136 KB Output is correct
13 Correct 431 ms 94156 KB Output is correct
14 Correct 430 ms 94216 KB Output is correct
15 Correct 434 ms 94184 KB Output is correct
16 Correct 437 ms 94012 KB Output is correct
17 Correct 430 ms 94012 KB Output is correct
18 Correct 458 ms 94012 KB Output is correct
19 Correct 151 ms 66200 KB Output is correct
20 Correct 441 ms 94160 KB Output is correct
21 Correct 428 ms 93876 KB Output is correct
22 Correct 153 ms 67792 KB Output is correct
23 Correct 190 ms 80024 KB Output is correct
24 Correct 160 ms 67948 KB Output is correct
25 Correct 155 ms 67836 KB Output is correct
26 Correct 221 ms 80612 KB Output is correct
27 Correct 161 ms 68520 KB Output is correct
28 Correct 156 ms 67748 KB Output is correct
29 Correct 163 ms 68576 KB Output is correct
30 Correct 154 ms 67740 KB Output is correct
31 Correct 188 ms 68564 KB Output is correct

Subtask #5
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 47296 KB Output is correct
2 Correct 24 ms 47580 KB Output is correct
3 Correct 23 ms 47496 KB Output is correct
4 Correct 22 ms 47316 KB Output is correct
5 Correct 23 ms 47548 KB Output is correct
6 Correct 23 ms 47576 KB Output is correct
7 Correct 24 ms 47256 KB Output is correct
8 Correct 24 ms 47308 KB Output is correct
9 Correct 23 ms 47560 KB Output is correct
10 Correct 23 ms 47564 KB Output is correct
11 Correct 26 ms 47568 KB Output is correct
12 Correct 24 ms 47544 KB Output is correct
13 Correct 23 ms 47528 KB Output is correct
14 Correct 25 ms 47580 KB Output is correct
15 Correct 22 ms 47600 KB Output is correct
16 Correct 260 ms 74360 KB Output is correct
17 Correct 544 ms 101552 KB Output is correct
18 Correct 54 ms 52488 KB Output is correct
19 Correct 215 ms 74964 KB Output is correct
20 Correct 535 ms 101548 KB Output is correct
21 Correct 348 ms 83412 KB Output is correct
22 Correct 228 ms 74364 KB Output is correct
23 Correct 555 ms 101496 KB Output is correct
24 Correct 542 ms 101560 KB Output is correct
25 Correct 532 ms 101544 KB Output is correct
26 Correct 209 ms 74760 KB Output is correct
27 Correct 216 ms 74868 KB Output is correct
28 Correct 209 ms 74704 KB Output is correct
29 Correct 211 ms 74812 KB Output is correct
30 Correct 216 ms 74944 KB Output is correct
31 Correct 25 ms 47260 KB Output is correct
32 Correct 22 ms 47284 KB Output is correct
33 Correct 23 ms 47208 KB Output is correct
34 Correct 22 ms 47316 KB Output is correct
35 Correct 24 ms 47284 KB Output is correct
36 Correct 23 ms 47304 KB Output is correct
37 Correct 25 ms 47420 KB Output is correct
38 Correct 22 ms 47288 KB Output is correct
39 Correct 24 ms 47308 KB Output is correct
40 Correct 23 ms 47324 KB Output is correct
41 Correct 266 ms 75988 KB Output is correct
42 Correct 441 ms 94036 KB Output is correct
43 Correct 439 ms 94088 KB Output is correct
44 Correct 159 ms 68556 KB Output is correct
45 Correct 423 ms 94012 KB Output is correct
46 Correct 422 ms 94188 KB Output is correct
47 Correct 429 ms 94080 KB Output is correct
48 Correct 445 ms 93964 KB Output is correct
49 Correct 427 ms 94108 KB Output is correct
50 Correct 425 ms 94072 KB Output is correct
51 Correct 421 ms 94036 KB Output is correct
52 Correct 431 ms 94136 KB Output is correct
53 Correct 431 ms 94156 KB Output is correct
54 Correct 430 ms 94216 KB Output is correct
55 Correct 434 ms 94184 KB Output is correct
56 Correct 437 ms 94012 KB Output is correct
57 Correct 430 ms 94012 KB Output is correct
58 Correct 458 ms 94012 KB Output is correct
59 Correct 151 ms 66200 KB Output is correct
60 Correct 441 ms 94160 KB Output is correct
61 Correct 428 ms 93876 KB Output is correct
62 Correct 153 ms 67792 KB Output is correct
63 Correct 190 ms 80024 KB Output is correct
64 Correct 160 ms 67948 KB Output is correct
65 Correct 155 ms 67836 KB Output is correct
66 Correct 221 ms 80612 KB Output is correct
67 Correct 161 ms 68520 KB Output is correct
68 Correct 156 ms 67748 KB Output is correct
69 Correct 163 ms 68576 KB Output is correct
70 Correct 154 ms 67740 KB Output is correct
71 Correct 188 ms 68564 KB Output is correct
72 Correct 387 ms 83364 KB Output is correct
73 Correct 559 ms 101560 KB Output is correct
74 Correct 544 ms 101556 KB Output is correct
75 Correct 558 ms 101556 KB Output is correct
76 Correct 549 ms 101504 KB Output is correct
77 Correct 562 ms 101684 KB Output is correct
78 Correct 545 ms 101416 KB Output is correct
79 Correct 570 ms 101448 KB Output is correct
80 Correct 553 ms 101680 KB Output is correct
81 Correct 556 ms 101520 KB Output is correct
82 Correct 558 ms 101492 KB Output is correct
83 Correct 552 ms 101552 KB Output is correct
84 Correct 564 ms 101544 KB Output is correct
85 Correct 569 ms 101592 KB Output is correct
86 Correct 570 ms 101440 KB Output is correct
87 Correct 565 ms 101592 KB Output is correct
88 Correct 556 ms 101456 KB Output is correct
89 Correct 260 ms 74304 KB Output is correct
90 Correct 561 ms 101480 KB Output is correct
91 Correct 496 ms 101316 KB Output is correct
92 Correct 265 ms 75320 KB Output is correct
93 Correct 342 ms 88132 KB Output is correct
94 Correct 280 ms 75196 KB Output is correct
95 Correct 271 ms 75320 KB Output is correct
96 Correct 404 ms 90464 KB Output is correct
97 Correct 299 ms 76472 KB Output is correct
98 Correct 269 ms 75184 KB Output is correct
99 Correct 296 ms 76324 KB Output is correct
100 Correct 262 ms 75320 KB Output is correct