oj.uz

답안 #895935

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
895935 2023-12-31T07:11:46 Z thunopro Evacuation plan (IZhO18_plan) C++14
100 / 100
 661 ms 48872 KB 
#include<bits/stdc++.h>
using namespace std ; 
#define ll long long 
#define maxn 200009 
#define fi first 
#define se second 
#define pb push_back 
#define left id<<1 
#define right id<<1|1 
#define re exit(0); 
#define _lower(x) lower_bound(v.begin(),v.end(),x)-v.begin()+1  

const int mod = 1e9+7 ; 
const int INF = 1e9 ; 
const int LOG = 18 ; 

typedef vector<int> vi ; 
typedef pair<int,int> pii ; 
typedef vector<ll> vl ; 
typedef vector<pii> vii ; 
 
void add ( int &a , int b ) 
{
	a += b ;
	if ( a < 0 ) a += mod ; 
	if ( a >= mod ) a -= mod ; 
}

template < typename T > void chkmin ( T &a , T b ) { if ( a > b ) a = b ; } 
template < typename T > void chkmax ( T &a , T b ) { if ( a < b ) a = b ; } 

void rf () 
{
	freopen ("bai1.inp","r",stdin) ; 
//	freopen ("bai1.out","w",stdout) ; 
}

int _pow ( int a , int n ) 
{
	if ( n == 0 ) return 1 ; 
	int res = _pow (a,n/2) ; 
	if ( n % 2 ) return 1ll*res*res%mod*a%mod ; 
	else return 1ll*res*res%mod ; 
}

int n , m , nq; 

vii adjList [maxn] ;
struct query {
	int s , t ;
}q [maxn] ; 
int d [maxn] ; 
pii vertex [maxn] ; 

struct shape {
	int u , d ; 
	bool operator < ( const shape &o ) const {
		return d>o.d ; 
	}
};
void prepare () 
{
	priority_queue <shape> S ; 
	memset ( d , 0x3f , sizeof d ) ; 
	int num ; cin >> num ; 
	for ( int i = 1 ; i <= num ; i ++ ) 
	{
		int x ; cin >> x ; 
		S . push ({x,d[x]=0}) ; 
	}
	
	while (!S.empty()) 
	{
		shape t = S.top() ; S.pop() ; 
		int u =t.u ; 
		if (t.d!=d[u]) continue ; 
		for ( auto x : adjList [u] ) 
		{
			int v =x.fi , w=x.se ; 
			if ( d[v] >d[u]+w) S . push ({v,d[v]=d[u]+w}) ; 
		}
	}
	for ( int i = 1 ; i <= n ; i ++ ) vertex [i] = {d[i],i} ; 
	sort (vertex+1,vertex+n+1,greater<pii>()) ; 
}

vi to_check [maxn] ; 
int L [maxn] , R [maxn] ; 

int lab [maxn] ; 
int find ( int u ) 
{
	return (lab[u]<0)?u:lab[u]=find(lab[u]) ; 
}
void uni ( int u , int v ) 
{
	if ( (u=find(u))==(v=find(v))) return ; 
	if ( lab[u]>lab[v] ) swap (u,v) ; 
	lab [u] += lab [v] ; 
	lab [v] = u ; 
}

bool used [maxn] ; 
void add_vertex ( int u ) 
{
	for ( auto x : adjList [u] ) 
	{
		int v = x.fi ; 
		if ( used [v] ) uni (u,v) ; 
	}
}
int main () 
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);cout.tie(0) ; 
//	rf () ; 
	cin >> n >> m ; 
	for ( int i = 1 ; i <= m ; i ++ ) 
	{
		int u , v , w ; cin >> u >> v >> w ; 
		adjList [u] . pb ({v,w}) ; 
		adjList [v] . pb ({u,w}) ; 
	}
	
	prepare () ; 
	
	cin >> nq ; 
	for ( int i = 1 ; i <= nq ; i ++ ) 
	{
		cin >> q[i].s >> q [i].t ; 
	}
	
	for ( int i = 1 ; i <= nq ; i ++ ) L [i] = 1 , R [i] = n ; 

	while ( true )
	{
		bool changed = false ; 
		for ( int i = 1 ; i <= nq ; i ++ ) 
		{
			if ( L[i]!=R[i] ) 
			{
				to_check [(L[i]+R[i])/2] . pb (i) ; 
				changed = true ; 
			}
		}
		for ( int i = 1 ; i <= n ; i ++ ) lab [i] = - 1 , used [i] = false ; 
		
		for ( int i = 1 ; i <= n ; i ++ ) 
		{
			used [vertex[i].se] = true ; 
			add_vertex (vertex[i].se) ; 
			while (!to_check[i].empty()) 
			{
				int id = to_check[i].back() ; to_check[i].pop_back() ; 
				if ( find (q[id].s) == find (q[id].t) ) R[id] = i ; 
				else L [id] = i+1 ;  
			}
		}
		if ( changed == false ) break ; 
	}
	
	for ( int i = 1 ; i <= nq ; i ++ ) cout << vertex[L[i]].fi << "\n" ; 
}

// range , error , check speical , ... 
// find key , find key 
//'-std=c++11' stay hard 
// there is no tomorrow

Compilation message

plan.cpp: In function 'void rf()':
plan.cpp:34:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |  freopen ("bai1.inp","r",stdin) ;
      |  ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 15964 KB Output is correct
2 Correct 4 ms 16220 KB Output is correct
3 Correct 4 ms 16220 KB Output is correct
4 Correct 4 ms 15964 KB Output is correct
5 Correct 4 ms 16472 KB Output is correct
6 Correct 4 ms 16264 KB Output is correct
7 Correct 3 ms 15960 KB Output is correct
8 Correct 3 ms 15964 KB Output is correct
9 Correct 4 ms 16200 KB Output is correct
10 Correct 4 ms 16220 KB Output is correct
11 Correct 4 ms 16220 KB Output is correct
12 Correct 4 ms 16220 KB Output is correct
13 Correct 5 ms 16220 KB Output is correct
14 Correct 4 ms 16220 KB Output is correct
15 Correct 4 ms 16148 KB Output is correct

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 15964 KB Output is correct
2 Correct 4 ms 16220 KB Output is correct
3 Correct 4 ms 16220 KB Output is correct
4 Correct 4 ms 15964 KB Output is correct
5 Correct 4 ms 16472 KB Output is correct
6 Correct 4 ms 16264 KB Output is correct
7 Correct 3 ms 15960 KB Output is correct
8 Correct 3 ms 15964 KB Output is correct
9 Correct 4 ms 16200 KB Output is correct
10 Correct 4 ms 16220 KB Output is correct
11 Correct 4 ms 16220 KB Output is correct
12 Correct 4 ms 16220 KB Output is correct
13 Correct 5 ms 16220 KB Output is correct
14 Correct 4 ms 16220 KB Output is correct
15 Correct 4 ms 16148 KB Output is correct
16 Correct 187 ms 32528 KB Output is correct
17 Correct 548 ms 48712 KB Output is correct
18 Correct 34 ms 18928 KB Output is correct
19 Correct 105 ms 30768 KB Output is correct
20 Correct 583 ms 48444 KB Output is correct
21 Correct 279 ms 37044 KB Output is correct
22 Correct 129 ms 33228 KB Output is correct
23 Correct 613 ms 48416 KB Output is correct
24 Correct 533 ms 48604 KB Output is correct
25 Correct 588 ms 48644 KB Output is correct
26 Correct 122 ms 30524 KB Output is correct
27 Correct 119 ms 30400 KB Output is correct
28 Correct 94 ms 30524 KB Output is correct
29 Correct 98 ms 30684 KB Output is correct
30 Correct 124 ms 30660 KB Output is correct

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 15960 KB Output is correct
2 Correct 3 ms 15964 KB Output is correct
3 Correct 3 ms 15964 KB Output is correct
4 Correct 3 ms 15964 KB Output is correct
5 Correct 3 ms 16144 KB Output is correct
6 Correct 4 ms 15960 KB Output is correct
7 Correct 4 ms 15964 KB Output is correct
8 Correct 3 ms 15964 KB Output is correct
9 Correct 3 ms 15964 KB Output is correct
10 Correct 3 ms 15964 KB Output is correct

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 212 ms 26052 KB Output is correct
2 Correct 475 ms 38624 KB Output is correct
3 Correct 510 ms 38776 KB Output is correct
4 Correct 54 ms 20956 KB Output is correct
5 Correct 480 ms 38516 KB Output is correct
6 Correct 446 ms 38296 KB Output is correct
7 Correct 441 ms 38548 KB Output is correct
8 Correct 500 ms 38516 KB Output is correct
9 Correct 490 ms 38380 KB Output is correct
10 Correct 444 ms 38748 KB Output is correct
11 Correct 558 ms 38656 KB Output is correct
12 Correct 455 ms 38632 KB Output is correct
13 Correct 528 ms 38488 KB Output is correct
14 Correct 508 ms 38532 KB Output is correct
15 Correct 442 ms 38548 KB Output is correct
16 Correct 473 ms 38688 KB Output is correct
17 Correct 475 ms 38388 KB Output is correct
18 Correct 484 ms 38516 KB Output is correct
19 Correct 59 ms 20820 KB Output is correct
20 Correct 505 ms 38616 KB Output is correct
21 Correct 401 ms 38908 KB Output is correct
22 Correct 61 ms 21816 KB Output is correct
23 Correct 88 ms 21332 KB Output is correct
24 Correct 60 ms 21824 KB Output is correct
25 Correct 62 ms 21788 KB Output is correct
26 Correct 122 ms 21604 KB Output is correct
27 Correct 57 ms 20948 KB Output is correct
28 Correct 65 ms 21744 KB Output is correct
29 Correct 54 ms 20828 KB Output is correct
30 Correct 61 ms 21808 KB Output is correct
31 Correct 68 ms 21120 KB Output is correct

Subtask #5
46.0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 15964 KB Output is correct
2 Correct 4 ms 16220 KB Output is correct
3 Correct 4 ms 16220 KB Output is correct
4 Correct 4 ms 15964 KB Output is correct
5 Correct 4 ms 16472 KB Output is correct
6 Correct 4 ms 16264 KB Output is correct
7 Correct 3 ms 15960 KB Output is correct
8 Correct 3 ms 15964 KB Output is correct
9 Correct 4 ms 16200 KB Output is correct
10 Correct 4 ms 16220 KB Output is correct
11 Correct 4 ms 16220 KB Output is correct
12 Correct 4 ms 16220 KB Output is correct
13 Correct 5 ms 16220 KB Output is correct
14 Correct 4 ms 16220 KB Output is correct
15 Correct 4 ms 16148 KB Output is correct
16 Correct 187 ms 32528 KB Output is correct
17 Correct 548 ms 48712 KB Output is correct
18 Correct 34 ms 18928 KB Output is correct
19 Correct 105 ms 30768 KB Output is correct
20 Correct 583 ms 48444 KB Output is correct
21 Correct 279 ms 37044 KB Output is correct
22 Correct 129 ms 33228 KB Output is correct
23 Correct 613 ms 48416 KB Output is correct
24 Correct 533 ms 48604 KB Output is correct
25 Correct 588 ms 48644 KB Output is correct
26 Correct 122 ms 30524 KB Output is correct
27 Correct 119 ms 30400 KB Output is correct
28 Correct 94 ms 30524 KB Output is correct
29 Correct 98 ms 30684 KB Output is correct
30 Correct 124 ms 30660 KB Output is correct
31 Correct 3 ms 15960 KB Output is correct
32 Correct 3 ms 15964 KB Output is correct
33 Correct 3 ms 15964 KB Output is correct
34 Correct 3 ms 15964 KB Output is correct
35 Correct 3 ms 16144 KB Output is correct
36 Correct 4 ms 15960 KB Output is correct
37 Correct 4 ms 15964 KB Output is correct
38 Correct 3 ms 15964 KB Output is correct
39 Correct 3 ms 15964 KB Output is correct
40 Correct 3 ms 15964 KB Output is correct
41 Correct 212 ms 26052 KB Output is correct
42 Correct 475 ms 38624 KB Output is correct
43 Correct 510 ms 38776 KB Output is correct
44 Correct 54 ms 20956 KB Output is correct
45 Correct 480 ms 38516 KB Output is correct
46 Correct 446 ms 38296 KB Output is correct
47 Correct 441 ms 38548 KB Output is correct
48 Correct 500 ms 38516 KB Output is correct
49 Correct 490 ms 38380 KB Output is correct
50 Correct 444 ms 38748 KB Output is correct
51 Correct 558 ms 38656 KB Output is correct
52 Correct 455 ms 38632 KB Output is correct
53 Correct 528 ms 38488 KB Output is correct
54 Correct 508 ms 38532 KB Output is correct
55 Correct 442 ms 38548 KB Output is correct
56 Correct 473 ms 38688 KB Output is correct
57 Correct 475 ms 38388 KB Output is correct
58 Correct 484 ms 38516 KB Output is correct
59 Correct 59 ms 20820 KB Output is correct
60 Correct 505 ms 38616 KB Output is correct
61 Correct 401 ms 38908 KB Output is correct
62 Correct 61 ms 21816 KB Output is correct
63 Correct 88 ms 21332 KB Output is correct
64 Correct 60 ms 21824 KB Output is correct
65 Correct 62 ms 21788 KB Output is correct
66 Correct 122 ms 21604 KB Output is correct
67 Correct 57 ms 20948 KB Output is correct
68 Correct 65 ms 21744 KB Output is correct
69 Correct 54 ms 20828 KB Output is correct
70 Correct 61 ms 21808 KB Output is correct
71 Correct 68 ms 21120 KB Output is correct
72 Correct 346 ms 36772 KB Output is correct
73 Correct 661 ms 48624 KB Output is correct
74 Correct 587 ms 48600 KB Output is correct
75 Correct 559 ms 48608 KB Output is correct
76 Correct 633 ms 48352 KB Output is correct
77 Correct 559 ms 48764 KB Output is correct
78 Correct 648 ms 48448 KB Output is correct
79 Correct 605 ms 48624 KB Output is correct
80 Correct 629 ms 48492 KB Output is correct
81 Correct 618 ms 48356 KB Output is correct
82 Correct 599 ms 48412 KB Output is correct
83 Correct 565 ms 48396 KB Output is correct
84 Correct 567 ms 48468 KB Output is correct
85 Correct 617 ms 48608 KB Output is correct
86 Correct 581 ms 48384 KB Output is correct
87 Correct 623 ms 48572 KB Output is correct
88 Correct 636 ms 48872 KB Output is correct
89 Correct 128 ms 33172 KB Output is correct
90 Correct 606 ms 48368 KB Output is correct
91 Correct 533 ms 48636 KB Output is correct
92 Correct 110 ms 30632 KB Output is correct
93 Correct 152 ms 31372 KB Output is correct
94 Correct 127 ms 30272 KB Output is correct
95 Correct 99 ms 30664 KB Output is correct
96 Correct 167 ms 30200 KB Output is correct
97 Correct 141 ms 31564 KB Output is correct
98 Correct 96 ms 30596 KB Output is correct
99 Correct 135 ms 31940 KB Output is correct
100 Correct 113 ms 30292 KB Output is correct