oj.uz

Submission #42512

# Submission time Handle Problem Language Result Execution time Memory
42512 2018-02-28T03:05:11 Z wzy Evacuation plan (IZhO18_plan) C++11
0 / 100
 602 ms 44804 KB 
#include <bits/stdc++.h>
using namespace std;
#define F first
#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 = 1000000000;
	for(int i = 21 ; i >= 0 ; i--){
		while(h[x]  >= h[y] + (1<<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;
}

int main(){
	scanf("%d%d" , &n,  &m);
	vector<edges> v;
	for(int i = 0 ; i <n;i++){
		pai[i] = i , peso[i] = 0 , d[i] = (int) 1e9;
	}
	for(int i = 0 ; i < m ; i++){
		int x,y,z;
		scanf("%d%d%d" , &x , &y , &z);
		x--, y--;
		v.pb({x,y,z});
		adj[x].pb(pii(z,y));
		adj[y].pb(pii(z,x));
	}
	scanf("%d" , &k);
	priority_queue<pii , vector<pii> , greater<pii> > pq;
	for(int i = 0 ; i < k ; i++) {
		int x;
		scanf("%d" , &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("%d" , &q);
	while(q--){
		int x,y;
		scanf("%d%d" , &x , &y);
		x-- ,y--;
		printf("%d\n" , query(x,y));
	}
}

Compilation message

plan.cpp: In function 'void pre(int, int)':
plan.cpp:21:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int y = 0 ; y < adj[i].size();y++){
                  ~~^~~~~~~~~~~~~~~
plan.cpp: In function 'int main()':
plan.cpp:89:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0 ; j < adj[u.S].size();j++){
                   ~~^~~~~~~~~~~~~~~~~
plan.cpp:63:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d" , &n,  &m);
  ~~~~~^~~~~~~~~~~~~~~~~~
plan.cpp:70:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d" , &x , &y , &z);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
plan.cpp:76:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d" , &k);
  ~~~~~^~~~~~~~~~~
plan.cpp:80:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d" , &x);
   ~~~~~^~~~~~~~~~~
plan.cpp:124:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d" , &q);
  ~~~~~^~~~~~~~~~~
plan.cpp:127:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d" , &x , &y);
   ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 20348 KB Output is correct
2 Correct 29 ms 20344 KB Output is correct
3 Correct 28 ms 20344 KB Output is correct
4 Correct 27 ms 20260 KB Output is correct
5 Correct 28 ms 20344 KB Output is correct
6 Correct 28 ms 20344 KB Output is correct
7 Correct 27 ms 20344 KB Output is correct
8 Correct 28 ms 20344 KB Output is correct
9 Correct 28 ms 20344 KB Output is correct
10 Correct 28 ms 20312 KB Output is correct
11 Correct 28 ms 20344 KB Output is correct
12 Correct 28 ms 20344 KB Output is correct
13 Incorrect 26 ms 20344 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 20348 KB Output is correct
2 Correct 29 ms 20344 KB Output is correct
3 Correct 28 ms 20344 KB Output is correct
4 Correct 27 ms 20260 KB Output is correct
5 Correct 28 ms 20344 KB Output is correct
6 Correct 28 ms 20344 KB Output is correct
7 Correct 27 ms 20344 KB Output is correct
8 Correct 28 ms 20344 KB Output is correct
9 Correct 28 ms 20344 KB Output is correct
10 Correct 28 ms 20312 KB Output is correct
11 Correct 28 ms 20344 KB Output is correct
12 Correct 28 ms 20344 KB Output is correct
13 Incorrect 26 ms 20344 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 20336 KB Output is correct
2 Incorrect 27 ms 20344 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 290 ms 32136 KB Output is correct
2 Correct 597 ms 44632 KB Output is correct
3 Correct 602 ms 44804 KB Output is correct
4 Incorrect 165 ms 29836 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 20348 KB Output is correct
2 Correct 29 ms 20344 KB Output is correct
3 Correct 28 ms 20344 KB Output is correct
4 Correct 27 ms 20260 KB Output is correct
5 Correct 28 ms 20344 KB Output is correct
6 Correct 28 ms 20344 KB Output is correct
7 Correct 27 ms 20344 KB Output is correct
8 Correct 28 ms 20344 KB Output is correct
9 Correct 28 ms 20344 KB Output is correct
10 Correct 28 ms 20312 KB Output is correct
11 Correct 28 ms 20344 KB Output is correct
12 Correct 28 ms 20344 KB Output is correct
13 Incorrect 26 ms 20344 KB Output isn't correct
14 Halted 0 ms 0 KB -