oj.uz

답안 #378530

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
378530 2021-03-17T01:31:05 Z iris2617 Evacuation plan (IZhO18_plan) C++14
100 / 100
 798 ms 59904 KB 
#include<bits/stdc++.h>
#define int long long
#define matsuri pair<int,int>
#define iris 1000000007
using namespace std;

vector<matsuri> G[100010];
int dis[100010];
priority_queue<matsuri, vector<matsuri>, greater<matsuri> > pq;
int id[100010];
bitset<100010> v;

int x;
set<int> s[100010];
int ds[100010],sz[100010],ans[100010];

bool cmp(int a,int b)
{
	return dis[a]>dis[b];
}

int fnd(int a)
{
	return ds[a] = ds[a]==a ? a : fnd(ds[a]);
}

void unn(int a,int b)
{
	a=fnd(a);
	b=fnd(b);
	if(a==b)
		return;
	if(sz[a]<sz[b])
		swap(a,b);
	ds[b]=a;
	sz[a]+=sz[b];
	for(int sana:s[b])
	{
		if(s[a].find(sana)==s[a].end())
			s[a].insert(sana);
		else
		{
			s[a].erase(sana);
			ans[sana]=x;
		}
	}
}

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int n,m,a,b,c,k,i,q;
	
	cin>>n>>m;
	while(m--)
	{
		cin>>a>>b>>c;
		G[a].emplace_back(b,c);
		G[b].emplace_back(a,c);
	}
	for(i=1;i<=n;i++)
	{
		dis[i]=1e15;
		id[i]=i;
		ds[i]=i;
		sz[i]=1;
	}
	cin>>k;
	for(i=0;i<k;i++)
	{
		cin>>a;
		dis[a]=0;
		pq.push({0,a});
	}
	while(!pq.empty())
	{
		a=pq.top().second;
		c=pq.top().first;
		pq.pop();
		if(c!=dis[a])
			continue;
		for(auto sana:G[a])
		{
			b=sana.first;
			c=sana.second;
			if(dis[a]+c<dis[b])
			{
				dis[b]=dis[a]+c;
				pq.push({dis[b], b});
			}
		}
	}
	sort(id+1,id+1+n,cmp);
	cin>>q;
	for(i=1;i<=q;i++)
	{
		cin>>a>>b;
		s[a].insert(i);
		s[b].insert(i);
	}
	for(i=1;i<=n;i++)
	{
		a=id[i];
		v[a]=1;
		x=dis[a];
		for(auto sana:G[a])
		{
			b=sana.first;
			if(v[b])
			{
				unn(a,b);
			}
		}
	}
	for(i=1;i<=q;i++)
	{
		cout<<ans[i]<<'\n';
	}
	
	return 0;
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 7404 KB Output is correct
2 Correct 7 ms 7660 KB Output is correct
3 Correct 7 ms 7660 KB Output is correct
4 Correct 5 ms 7404 KB Output is correct
5 Correct 7 ms 7660 KB Output is correct
6 Correct 9 ms 7660 KB Output is correct
7 Correct 5 ms 7404 KB Output is correct
8 Correct 5 ms 7404 KB Output is correct
9 Correct 7 ms 7660 KB Output is correct
10 Correct 7 ms 7660 KB Output is correct
11 Correct 7 ms 7660 KB Output is correct
12 Correct 7 ms 7660 KB Output is correct
13 Correct 7 ms 7660 KB Output is correct
14 Correct 7 ms 7660 KB Output is correct
15 Correct 7 ms 7808 KB Output is correct

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 7404 KB Output is correct
2 Correct 7 ms 7660 KB Output is correct
3 Correct 7 ms 7660 KB Output is correct
4 Correct 5 ms 7404 KB Output is correct
5 Correct 7 ms 7660 KB Output is correct
6 Correct 9 ms 7660 KB Output is correct
7 Correct 5 ms 7404 KB Output is correct
8 Correct 5 ms 7404 KB Output is correct
9 Correct 7 ms 7660 KB Output is correct
10 Correct 7 ms 7660 KB Output is correct
11 Correct 7 ms 7660 KB Output is correct
12 Correct 7 ms 7660 KB Output is correct
13 Correct 7 ms 7660 KB Output is correct
14 Correct 7 ms 7660 KB Output is correct
15 Correct 7 ms 7808 KB Output is correct
16 Correct 293 ms 29028 KB Output is correct
17 Correct 798 ms 58848 KB Output is correct
18 Correct 43 ms 12012 KB Output is correct
19 Correct 246 ms 30300 KB Output is correct
20 Correct 773 ms 58980 KB Output is correct
21 Correct 509 ms 40524 KB Output is correct
22 Correct 201 ms 29164 KB Output is correct
23 Correct 744 ms 58984 KB Output is correct
24 Correct 750 ms 58852 KB Output is correct
25 Correct 763 ms 58848 KB Output is correct
26 Correct 255 ms 30044 KB Output is correct
27 Correct 263 ms 30172 KB Output is correct
28 Correct 270 ms 30044 KB Output is correct
29 Correct 262 ms 30172 KB Output is correct
30 Correct 265 ms 30256 KB Output is correct

Subtask #3
12.0 / 12.0

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

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 246 ms 23524 KB Output is correct
2 Correct 469 ms 39568 KB Output is correct
3 Correct 463 ms 39520 KB Output is correct
4 Correct 87 ms 15980 KB Output is correct
5 Correct 462 ms 39480 KB Output is correct
6 Correct 492 ms 39524 KB Output is correct
7 Correct 488 ms 39592 KB Output is correct
8 Correct 492 ms 39580 KB Output is correct
9 Correct 526 ms 39528 KB Output is correct
10 Correct 470 ms 39528 KB Output is correct
11 Correct 462 ms 39528 KB Output is correct
12 Correct 470 ms 39528 KB Output is correct
13 Correct 485 ms 39528 KB Output is correct
14 Correct 474 ms 39652 KB Output is correct
15 Correct 469 ms 41564 KB Output is correct
16 Correct 461 ms 39504 KB Output is correct
17 Correct 489 ms 39796 KB Output is correct
18 Correct 475 ms 39524 KB Output is correct
19 Correct 88 ms 15980 KB Output is correct
20 Correct 476 ms 39656 KB Output is correct
21 Correct 448 ms 39752 KB Output is correct
22 Correct 112 ms 19164 KB Output is correct
23 Correct 110 ms 16588 KB Output is correct
24 Correct 118 ms 19152 KB Output is correct
25 Correct 117 ms 19160 KB Output is correct
26 Correct 118 ms 16916 KB Output is correct
27 Correct 85 ms 16176 KB Output is correct
28 Correct 112 ms 19228 KB Output is correct
29 Correct 107 ms 16184 KB Output is correct
30 Correct 113 ms 19164 KB Output is correct
31 Correct 93 ms 16108 KB Output is correct

Subtask #5
46.0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 7404 KB Output is correct
2 Correct 7 ms 7660 KB Output is correct
3 Correct 7 ms 7660 KB Output is correct
4 Correct 5 ms 7404 KB Output is correct
5 Correct 7 ms 7660 KB Output is correct
6 Correct 9 ms 7660 KB Output is correct
7 Correct 5 ms 7404 KB Output is correct
8 Correct 5 ms 7404 KB Output is correct
9 Correct 7 ms 7660 KB Output is correct
10 Correct 7 ms 7660 KB Output is correct
11 Correct 7 ms 7660 KB Output is correct
12 Correct 7 ms 7660 KB Output is correct
13 Correct 7 ms 7660 KB Output is correct
14 Correct 7 ms 7660 KB Output is correct
15 Correct 7 ms 7808 KB Output is correct
16 Correct 293 ms 29028 KB Output is correct
17 Correct 798 ms 58848 KB Output is correct
18 Correct 43 ms 12012 KB Output is correct
19 Correct 246 ms 30300 KB Output is correct
20 Correct 773 ms 58980 KB Output is correct
21 Correct 509 ms 40524 KB Output is correct
22 Correct 201 ms 29164 KB Output is correct
23 Correct 744 ms 58984 KB Output is correct
24 Correct 750 ms 58852 KB Output is correct
25 Correct 763 ms 58848 KB Output is correct
26 Correct 255 ms 30044 KB Output is correct
27 Correct 263 ms 30172 KB Output is correct
28 Correct 270 ms 30044 KB Output is correct
29 Correct 262 ms 30172 KB Output is correct
30 Correct 265 ms 30256 KB Output is correct
31 Correct 6 ms 7404 KB Output is correct
32 Correct 5 ms 7404 KB Output is correct
33 Correct 6 ms 7404 KB Output is correct
34 Correct 6 ms 7456 KB Output is correct
35 Correct 6 ms 7404 KB Output is correct
36 Correct 6 ms 7404 KB Output is correct
37 Correct 6 ms 7408 KB Output is correct
38 Correct 5 ms 7404 KB Output is correct
39 Correct 5 ms 7404 KB Output is correct
40 Correct 5 ms 7404 KB Output is correct
41 Correct 246 ms 23524 KB Output is correct
42 Correct 469 ms 39568 KB Output is correct
43 Correct 463 ms 39520 KB Output is correct
44 Correct 87 ms 15980 KB Output is correct
45 Correct 462 ms 39480 KB Output is correct
46 Correct 492 ms 39524 KB Output is correct
47 Correct 488 ms 39592 KB Output is correct
48 Correct 492 ms 39580 KB Output is correct
49 Correct 526 ms 39528 KB Output is correct
50 Correct 470 ms 39528 KB Output is correct
51 Correct 462 ms 39528 KB Output is correct
52 Correct 470 ms 39528 KB Output is correct
53 Correct 485 ms 39528 KB Output is correct
54 Correct 474 ms 39652 KB Output is correct
55 Correct 469 ms 41564 KB Output is correct
56 Correct 461 ms 39504 KB Output is correct
57 Correct 489 ms 39796 KB Output is correct
58 Correct 475 ms 39524 KB Output is correct
59 Correct 88 ms 15980 KB Output is correct
60 Correct 476 ms 39656 KB Output is correct
61 Correct 448 ms 39752 KB Output is correct
62 Correct 112 ms 19164 KB Output is correct
63 Correct 110 ms 16588 KB Output is correct
64 Correct 118 ms 19152 KB Output is correct
65 Correct 117 ms 19160 KB Output is correct
66 Correct 118 ms 16916 KB Output is correct
67 Correct 85 ms 16176 KB Output is correct
68 Correct 112 ms 19228 KB Output is correct
69 Correct 107 ms 16184 KB Output is correct
70 Correct 113 ms 19164 KB Output is correct
71 Correct 93 ms 16108 KB Output is correct
72 Correct 605 ms 42856 KB Output is correct
73 Correct 798 ms 59872 KB Output is correct
74 Correct 753 ms 59616 KB Output is correct
75 Correct 785 ms 59848 KB Output is correct
76 Correct 768 ms 59748 KB Output is correct
77 Correct 749 ms 59620 KB Output is correct
78 Correct 750 ms 59748 KB Output is correct
79 Correct 763 ms 59904 KB Output is correct
80 Correct 784 ms 59748 KB Output is correct
81 Correct 765 ms 59616 KB Output is correct
82 Correct 782 ms 59744 KB Output is correct
83 Correct 757 ms 59564 KB Output is correct
84 Correct 747 ms 59740 KB Output is correct
85 Correct 739 ms 59740 KB Output is correct
86 Correct 739 ms 59612 KB Output is correct
87 Correct 739 ms 59616 KB Output is correct
88 Correct 772 ms 59876 KB Output is correct
89 Correct 299 ms 31596 KB Output is correct
90 Correct 753 ms 59616 KB Output is correct
91 Correct 758 ms 59364 KB Output is correct
92 Correct 340 ms 32524 KB Output is correct
93 Correct 446 ms 56556 KB Output is correct
94 Correct 329 ms 32476 KB Output is correct
95 Correct 317 ms 32616 KB Output is correct
96 Correct 503 ms 59884 KB Output is correct
97 Correct 332 ms 33644 KB Output is correct
98 Correct 337 ms 32476 KB Output is correct
99 Correct 352 ms 33660 KB Output is correct
100 Correct 323 ms 32604 KB Output is correct