oj.uz

Submission #42528

# Submission time Handle Problem Language Result Execution time Memory
42528 2018-02-28T03:35:09 Z wzy Evacuation plan (IZhO18_plan) C++11
0 / 100
 698 ms 83208 KB 
#include <bits/stdc++.h>
using namespace std;
#define F first
#define int long long
#define S second
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
int n , m , k , d[100005] , pai[100005] , peso[100005] , fn[100005] , sparse[100005][22] , custo[100005] , anc[100005][22] , h[100005];
vector<pii> adj[100005];
struct edges{
	int x , y, z;
};


bool cmp(edges a , edges b){
	return a.z > b.z;
}

void pre(int i , int j){
	if(i == j) h[i] = 0;
	for(int y = 0 ; y < adj[i].size();y++){
		pii v = adj[i][y];
		if(v.S == j) continue;
		fn[v.S] = i;
		custo[v.S] = v.F;
		h[v.S] = h[i] + 1;
		pre(v.S , i);
	}
}

int fd(int x){ return pai[x] == x ? x : pai[x] = fd(pai[x]);}

void join(int u , int v){
	u = fd(u) , v = fd(v);
	if(peso[u] > peso[v]) swap(u,v);
	pai[u] = v, peso[v] += peso[u] + 1;
}


int query(int x , int y){
	if(h[x] < h[y]) swap(x,y);
	int ansj = (int) 1e18;
	for(int i = 21 ; i >= 0 ; i--){
		while(h[x]  >= h[y] + (1LL<<i)){
			ansj = min(ansj , sparse[x][i]);
			x = anc[x][i];
		}
	}
	if(x == y) return ansj;
	for(int i = 21 ; i >= 0 ; i--){
		if(anc[x][i] != anc[y][i] && anc[x][i] != -1){
			ansj = min(ansj , sparse[x][i]);
			ansj = min(ansj , sparse[y][i]);
			x = anc[x][i] , y = anc[y][i];
		}
	}
	ansj = min(ansj , sparse[x][0]);
	ansj = min(ansj , sparse[y][0]);
	return ansj;
}

int32_t main(){
	scanf("%lld%lld" , &n,  &m);
	vector<edges> v;
	for(int i = 0 ; i <n;i++){
		pai[i] = i , peso[i] = 0 , d[i] = (int) 1e18;
	}
	for(int i = 0 ; i < m ; i++){
		int x,y,z;
		scanf("%lld%lld%lld" , &x , &y , &z);
		x--, y--;
		v.pb({x,y,z});
		adj[x].pb(pii(z,y));
		adj[y].pb(pii(z,x));
	}
	scanf("%lld" , &k);
	priority_queue<pii , vector<pii> , greater<pii> > pq;
	for(int i = 0 ; i < k ; i++) {
		int x;
		scanf("%lld" , &x);
		x--;
		d[x] = 0;
		pq.push(pii(0,x));
	}
	while(!pq.empty()){
		pii u = pq.top();
		pq.pop();
		if(d[u.S] != u.F) continue;
		for(int j = 0 ; j < adj[u.S].size();j++){
			pii v = adj[u.S][j];
			if(d[v.S] > v.F + u.F){
				d[v.S] = v.F + u.F;
				pq.push(pii(d[v.S] , v.S));
			}
		}
	}
	for(int i = 0 ; i < m ; i++){
		v[i].z = min(d[v[i].x] , d[v[i].y]);
		adj[v[i].x].clear();
		adj[v[i].y].clear();
	}
	sort(v.begin() , v.end() , cmp);
	for(int i = 0 ; i <m;i++){
		if(fd(v[i].x) != fd(v[i].y)){
			join(v[i].x , v[i].y);
			adj[v[i].x].pb(pii(v[i].z , v[i].y));
			adj[v[i].y].pb(pii(v[i].z , v[i].x));
		}
	}

	for(int i = 0 ; i < 100005 ; i++)
		for(int j = 0 ; j < 22 ; j++) anc[i][j] = -1 , sparse[i][j] = 1000000009;
	memset(fn , -1 , sizeof fn);
	pre(0 , 0);
	for(int i = 0 ; i < 100005 ; i++){
		if(fn[i] != -1) anc[i][0] = fn[i] , sparse[i][0] = custo[i];
	}
	for(int j = 1; j < 22 ; j++){
		for(int i = 0 ; i < 100005;i++){
			if(anc[i][j-1] != -1) anc[i][j] = anc[anc[i][j-1]][j-1] , sparse[i][j] = min(sparse[i][j] , min(sparse[i][j-1] , custo[anc[i][j-1]]));
		}
	}
	int q;
	scanf("%lld" , &q);
	while(q--){
		int x,y;
		scanf("%lld%lld" , &x , &y);
		x-- ,y--;
		printf("%lld\n" , query(x,y));
	}
}

Compilation message

plan.cpp: In function 'void pre(long long int, long long int)':
plan.cpp:22:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int y = 0 ; y < adj[i].size();y++){
                  ~~^~~~~~~~~~~~~~~
plan.cpp: In function 'int32_t main()':
plan.cpp:90:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0 ; j < adj[u.S].size();j++){
                   ~~^~~~~~~~~~~~~~~~~
plan.cpp:64:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld" , &n,  &m);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
plan.cpp:71:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld%lld" , &x , &y , &z);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
plan.cpp:77:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld" , &k);
  ~~~~~^~~~~~~~~~~~~
plan.cpp:81:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld" , &x);
   ~~~~~^~~~~~~~~~~~~
plan.cpp:125:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld" , &q);
  ~~~~~^~~~~~~~~~~~~
plan.cpp:128:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld" , &x , &y);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 37880 KB Output is correct
2 Correct 45 ms 38008 KB Output is correct
3 Correct 45 ms 38008 KB Output is correct
4 Correct 42 ms 37960 KB Output is correct
5 Correct 43 ms 38008 KB Output is correct
6 Correct 44 ms 38096 KB Output is correct
7 Correct 43 ms 37880 KB Output is correct
8 Correct 43 ms 37880 KB Output is correct
9 Correct 44 ms 38008 KB Output is correct
10 Correct 44 ms 38008 KB Output is correct
11 Correct 44 ms 38008 KB Output is correct
12 Correct 44 ms 38008 KB Output is correct
13 Incorrect 44 ms 38012 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 37880 KB Output is correct
2 Correct 45 ms 38008 KB Output is correct
3 Correct 45 ms 38008 KB Output is correct
4 Correct 42 ms 37960 KB Output is correct
5 Correct 43 ms 38008 KB Output is correct
6 Correct 44 ms 38096 KB Output is correct
7 Correct 43 ms 37880 KB Output is correct
8 Correct 43 ms 37880 KB Output is correct
9 Correct 44 ms 38008 KB Output is correct
10 Correct 44 ms 38008 KB Output is correct
11 Correct 44 ms 38008 KB Output is correct
12 Correct 44 ms 38008 KB Output is correct
13 Incorrect 44 ms 38012 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 37880 KB Output is correct
2 Incorrect 42 ms 37964 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 334 ms 59196 KB Output is correct
2 Correct 698 ms 83208 KB Output is correct
3 Correct 674 ms 83144 KB Output is correct
4 Incorrect 211 ms 51812 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 37880 KB Output is correct
2 Correct 45 ms 38008 KB Output is correct
3 Correct 45 ms 38008 KB Output is correct
4 Correct 42 ms 37960 KB Output is correct
5 Correct 43 ms 38008 KB Output is correct
6 Correct 44 ms 38096 KB Output is correct
7 Correct 43 ms 37880 KB Output is correct
8 Correct 43 ms 37880 KB Output is correct
9 Correct 44 ms 38008 KB Output is correct
10 Correct 44 ms 38008 KB Output is correct
11 Correct 44 ms 38008 KB Output is correct
12 Correct 44 ms 38008 KB Output is correct
13 Incorrect 44 ms 38012 KB Output isn't correct
14 Halted 0 ms 0 KB -