oj.uz

Submission #42551

# Submission time Handle Problem Language Result Execution time Memory
42551 2018-02-28T04:24:24 Z wzy Evacuation plan (IZhO18_plan) C++14
0 / 100
 692 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--){
		if(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++) custo[i] = (int) 1e18;
	for(int i = 0 ; i < 100005 ; i++)
		for(int j = 0 ; j < 22 ; j++) anc[i][j] = -1 , sparse[i][j] = (int) 1e18;
	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-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 43 ms 38652 KB Output is correct
2 Correct 44 ms 38776 KB Output is correct
3 Correct 44 ms 38776 KB Output is correct
4 Correct 43 ms 38676 KB Output is correct
5 Correct 45 ms 38776 KB Output is correct
6 Correct 44 ms 38776 KB Output is correct
7 Correct 44 ms 38760 KB Output is correct
8 Correct 44 ms 38768 KB Output is correct
9 Correct 45 ms 38736 KB Output is correct
10 Correct 45 ms 38880 KB Output is correct
11 Correct 53 ms 38776 KB Output is correct
12 Correct 45 ms 38904 KB Output is correct
13 Incorrect 46 ms 38776 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 38652 KB Output is correct
2 Correct 44 ms 38776 KB Output is correct
3 Correct 44 ms 38776 KB Output is correct
4 Correct 43 ms 38676 KB Output is correct
5 Correct 45 ms 38776 KB Output is correct
6 Correct 44 ms 38776 KB Output is correct
7 Correct 44 ms 38760 KB Output is correct
8 Correct 44 ms 38768 KB Output is correct
9 Correct 45 ms 38736 KB Output is correct
10 Correct 45 ms 38880 KB Output is correct
11 Correct 53 ms 38776 KB Output is correct
12 Correct 45 ms 38904 KB Output is correct
13 Incorrect 46 ms 38776 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 38672 KB Output is correct
2 Incorrect 45 ms 38648 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 350 ms 59276 KB Output is correct
2 Correct 677 ms 83152 KB Output is correct
3 Correct 692 ms 83208 KB Output is correct
4 Incorrect 216 ms 51760 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 38652 KB Output is correct
2 Correct 44 ms 38776 KB Output is correct
3 Correct 44 ms 38776 KB Output is correct
4 Correct 43 ms 38676 KB Output is correct
5 Correct 45 ms 38776 KB Output is correct
6 Correct 44 ms 38776 KB Output is correct
7 Correct 44 ms 38760 KB Output is correct
8 Correct 44 ms 38768 KB Output is correct
9 Correct 45 ms 38736 KB Output is correct
10 Correct 45 ms 38880 KB Output is correct
11 Correct 53 ms 38776 KB Output is correct
12 Correct 45 ms 38904 KB Output is correct
13 Incorrect 46 ms 38776 KB Output isn't correct
14 Halted 0 ms 0 KB -