oj.uz

Submission #671727

# Submission time Handle Problem Language Result Execution time Memory
671727 2022-12-13T15:42:30 Z smartmonky Evacuation plan (IZhO18_plan) C++14
41 / 100
 1147 ms 524288 KB 
#include <bits/stdc++.h>
  
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define int long long
using namespace std;
 
const int N = 2e6 + 10;
int d[N], ans[N], par[N], sz[N];
vector < pair <int,int> > g[N];
set <int> s[N];
int n;
int dji(int f, int s){
	vector <int> dist(n + 1, -1e9);
	set <pair <int,int> > st;
	st.insert({0, f});
	dist[f] = d[f];
	while (!st.empty()) {
		int v = (--st.end())->second;
		st.erase (--st.end());
		for (size_t j=0; j< g[v].size(); ++j) {
			int to = g[v][j].first;
			if (min(dist[v], d[to]) > dist[to]) {
				st.erase (make_pair (d[to], to));
				if(to == s){
					return  min(dist[v], d[to]);
				}
				dist[to] = min(dist[v], d[to]);
				st.insert (make_pair (d[to], to));
			}
		}
	}
}
int find(int a){
    if(par[a] == a)
        return a;
    return par[a] = find(par[a]);
}
void connect(int a, int b, int w){
    a = find(a);
    b = find(b);
    if(a == b)return;
    if(a != b){
        if(sz[a] < sz[b])
            swap(a,b);
        par[b] = a;
        sz[a] += sz[b];
    }
    if ((int) s[a].size() > (int) s[b].size()) swap(s[a] , s[b]);
 
    for (int x : s[b])
    {
        if (s[a].find(x) != s[a].end())
        {
            ans[x] = w;
            s[a].erase(x);
        }
        else
        {
            s[a].insert(x);
        }
    }
    
}
main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	memset(d, 0x3f3f, sizeof(d));
	int m;
	cin >> n >> m;
	for(int i = 1; i <= n; i++){
		par[i] = i;
		sz[i] = 1;
	}
	for(int i = 0; i < m; i++){
		int a, b, c;
		cin >> a >> b >> c;
		g[a].pb({b, c});
		g[b].pb({a, c});
	}
	int k;
	cin >> k;
	set <pair <int,int> > st;
	for(int i = 0; i < k; i++){
		int a;
		cin >> a;
		st.insert({0, a});
		d[a] = 0;
	}
	while (!st.empty()) {
		int v = st.begin()->second;
		st.erase (st.begin());
		for (size_t j=0; j<g[v].size(); ++j) {
			int to = g[v][j].first,
				len = g[v][j].second;
			if (d[v] + len < d[to]) {
				d[to] = d[v] + len;
				st.insert (make_pair (d[to], to));
			}
		}
	}
	vector <pair <int,int> > vp;
	for(int i = 1; i <= n; i++){
		vp.pb({d[i], i});
	}
	int q;
	cin >> q;
	for(int i = 1; i <= q; i++){
		int a, b;
		cin >> a >> b;
		s[a].insert(i);
		s[b].insert(i);
	}
	sort(rall(vp));
	 for (auto x : vp)
    {
        int w = x.first , u = x.second;
        for (auto adj : g[u])
        {
            int v = adj.ff;
            if (d[v] >= w) connect(u , v , w);
        }
    }
	for(int i = 1; i <= q; i++)cout << ans[i] << endl;
}

Compilation message

plan.cpp:68:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   68 | main(){
      | ^~~~
plan.cpp: In function 'long long int dji(long long int, long long int)':
plan.cpp:17:31: warning: control reaches end of non-void function [-Wreturn-type]
   17 |  vector <int> dist(n + 1, -1e9);
      |                               ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 156872 KB Output is correct
2 Correct 142 ms 180400 KB Output is correct
3 Correct 141 ms 180512 KB Output is correct
4 Correct 71 ms 156876 KB Output is correct
5 Correct 141 ms 180416 KB Output is correct
6 Correct 132 ms 180376 KB Output is correct
7 Correct 70 ms 156876 KB Output is correct
8 Correct 74 ms 156840 KB Output is correct
9 Correct 72 ms 157016 KB Output is correct
10 Correct 72 ms 157132 KB Output is correct
11 Correct 85 ms 157136 KB Output is correct
12 Correct 135 ms 180384 KB Output is correct
13 Correct 72 ms 157336 KB Output is correct
14 Correct 78 ms 157116 KB Output is correct
15 Correct 74 ms 157112 KB Output is correct

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 156872 KB Output is correct
2 Correct 142 ms 180400 KB Output is correct
3 Correct 141 ms 180512 KB Output is correct
4 Correct 71 ms 156876 KB Output is correct
5 Correct 141 ms 180416 KB Output is correct
6 Correct 132 ms 180376 KB Output is correct
7 Correct 70 ms 156876 KB Output is correct
8 Correct 74 ms 156840 KB Output is correct
9 Correct 72 ms 157016 KB Output is correct
10 Correct 72 ms 157132 KB Output is correct
11 Correct 85 ms 157136 KB Output is correct
12 Correct 135 ms 180384 KB Output is correct
13 Correct 72 ms 157336 KB Output is correct
14 Correct 78 ms 157116 KB Output is correct
15 Correct 74 ms 157112 KB Output is correct
16 Runtime error 1147 ms 524288 KB Execution killed with signal 9
17 Halted 0 ms 0 KB -

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 156900 KB Output is correct
2 Correct 69 ms 156872 KB Output is correct
3 Correct 79 ms 156944 KB Output is correct
4 Correct 71 ms 156876 KB Output is correct
5 Correct 72 ms 156856 KB Output is correct
6 Correct 69 ms 156884 KB Output is correct
7 Correct 72 ms 156812 KB Output is correct
8 Correct 73 ms 156780 KB Output is correct
9 Correct 71 ms 156944 KB Output is correct
10 Correct 76 ms 156816 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 271 ms 173752 KB Output is correct
2 Correct 550 ms 191572 KB Output is correct
3 Correct 521 ms 191508 KB Output is correct
4 Correct 157 ms 169456 KB Output is correct
5 Correct 521 ms 189876 KB Output is correct
6 Correct 516 ms 191448 KB Output is correct
7 Correct 511 ms 191436 KB Output is correct
8 Correct 517 ms 189916 KB Output is correct
9 Correct 523 ms 189864 KB Output is correct
10 Correct 528 ms 191408 KB Output is correct
11 Correct 533 ms 191512 KB Output is correct
12 Correct 560 ms 191684 KB Output is correct
13 Correct 539 ms 191384 KB Output is correct
14 Correct 525 ms 190044 KB Output is correct
15 Correct 532 ms 191820 KB Output is correct
16 Correct 540 ms 190000 KB Output is correct
17 Correct 529 ms 190004 KB Output is correct
18 Correct 543 ms 191560 KB Output is correct
19 Correct 149 ms 165220 KB Output is correct
20 Correct 650 ms 189944 KB Output is correct
21 Correct 419 ms 189308 KB Output is correct
22 Correct 183 ms 170952 KB Output is correct
23 Correct 148 ms 165648 KB Output is correct
24 Correct 169 ms 170808 KB Output is correct
25 Correct 168 ms 169320 KB Output is correct
26 Correct 164 ms 166048 KB Output is correct
27 Correct 143 ms 169380 KB Output is correct
28 Correct 166 ms 170808 KB Output is correct
29 Correct 143 ms 169344 KB Output is correct
30 Correct 167 ms 170940 KB Output is correct
31 Correct 145 ms 169328 KB Output is correct

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 156872 KB Output is correct
2 Correct 142 ms 180400 KB Output is correct
3 Correct 141 ms 180512 KB Output is correct
4 Correct 71 ms 156876 KB Output is correct
5 Correct 141 ms 180416 KB Output is correct
6 Correct 132 ms 180376 KB Output is correct
7 Correct 70 ms 156876 KB Output is correct
8 Correct 74 ms 156840 KB Output is correct
9 Correct 72 ms 157016 KB Output is correct
10 Correct 72 ms 157132 KB Output is correct
11 Correct 85 ms 157136 KB Output is correct
12 Correct 135 ms 180384 KB Output is correct
13 Correct 72 ms 157336 KB Output is correct
14 Correct 78 ms 157116 KB Output is correct
15 Correct 74 ms 157112 KB Output is correct
16 Runtime error 1147 ms 524288 KB Execution killed with signal 9
17 Halted 0 ms 0 KB -