oj.uz

Submission #681181

# Submission time Handle Problem Language Result Execution time Memory
681181 2023-01-12T13:42:06 Z arnold518 Reconstruction Project (JOI22_reconstruction) C++17
100 / 100
 4646 ms 98428 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 500;
const int MAXM = 1e5;
const int MAXQ = 1e6;
const ll INF = 1e18;

struct Edge
{
	int u, v; ll w;
};

int N, M, Q;
Edge A[MAXM+10];
int B[MAXQ+10];

struct UF
{
	int par[MAXN+10], sz[MAXN+10];
	void init()
	{
		for(int i=1; i<=N; i++) par[i]=i, sz[i]=1;
	}
	int Find(int x)
	{
		if(x==par[x]) return x;
		return par[x]=Find(par[x]);
	}
	void Union(int x, int y)
	{
		x=Find(x); y=Find(y);
		if(x==y) return;
		if(sz[x]>sz[y]) swap(x, y);
		if(sz[x]==sz[y]) sz[y]++;
		par[x]=y;
	}
};

ll ans[MAXQ+10];
int KL[MAXM+10], KR[MAXM+10];
map<ll, pll> MM;

pll operator + (const pll &p, const pll &q) { return pll(p.first+q.first, p.second+q.second); }

int main()
{
	scanf("%d%d", &N, &M);
	for(int i=1; i<=M; i++)
	{
		int u, v, w;
		scanf("%d%d%lld", &u, &v, &w); w*=2;
		A[i]={u, v, w};
	}
	sort(A+1, A+M+1, [&](const Edge &p, const Edge &q) { return p.w<q.w; });
	scanf("%d", &Q);
	for(int i=1; i<=Q; i++) scanf("%d", &B[i]), B[i]*=2;
	for(int i=1; i<=Q; i++) MM[B[i]];
	A[0].w=-INF, A[M+1].w=INF;

	for(int i=1; i<=M; i++) KR[i]=M+1, KL[i]=0;

	UF uf;
	vector<int> V;
	for(int i=M; i>=1; i--)
	{
		uf.init();
		for(auto it : V)
		{
			uf.Union(A[it].u, A[it].v);
			if(uf.Find(A[i].u)==uf.Find(A[i].v))
			{
				KR[i]=it;
				break;
			}
		}
		uf.init();
		uf.Union(A[i].u, A[i].v);
		vector<int> VV;
		VV.push_back(i);
		for(auto it : V)
		{
			if(uf.Find(A[it].u)==uf.Find(A[it].v)) continue;
			uf.Union(A[it].u, A[it].v);
			VV.push_back(it);
		}
		V=VV;
	}

	V.clear();
	for(int i=1; i<=M; i++)
	{
		uf.init();
		for(auto it : V)
		{
			uf.Union(A[it].u, A[it].v);
			if(uf.Find(A[i].u)==uf.Find(A[i].v))
			{
				KL[i]=it;
				break;
			}
		}
		uf.init();
		uf.Union(A[i].u, A[i].v);
		vector<int> VV;
		VV.push_back(i);
		for(auto it : V)
		{
			if(uf.Find(A[it].u)==uf.Find(A[it].v)) continue;
			uf.Union(A[it].u, A[it].v);
			VV.push_back(it);
		}
		V=VV;
	}

	for(int i=1; i<=M; i++)
	{
		ll l=A[KL[i]].w+A[i].w>>1;
		ll r=A[KR[i]].w+A[i].w>>1;
		//printf("%lld %lld %lld\n", l, A[i].w, r);

		MM[l]=MM[l]+pll(-1, A[i].w);
		MM[A[i].w]=MM[A[i].w]+pll(2, -2*A[i].w);
		MM[r]=MM[r]+pll(-1, A[i].w);
	}

	for(auto it=next(MM.begin()); it!=MM.end(); it++) it->second=it->second+prev(it)->second;

	for(int i=1; i<=Q; i++)
	{
		pll p=MM[B[i]];
		printf("%lld\n", (p.first*B[i]+p.second)/2);
	}
}

Compilation message

reconstruction.cpp: In function 'int main()':
reconstruction.cpp:56:17: warning: format '%lld' expects argument of type 'long long int*', but argument 4 has type 'int*' [-Wformat=]
   56 |   scanf("%d%d%lld", &u, &v, &w); w*=2;
      |              ~~~^           ~~
      |                 |           |
      |                 |           int*
      |                 long long int*
      |              %d
reconstruction.cpp:122:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  122 |   ll l=A[KL[i]].w+A[i].w>>1;
      |        ~~~~~~~~~~^~~~~~~
reconstruction.cpp:123:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  123 |   ll r=A[KR[i]].w+A[i].w>>1;
      |        ~~~~~~~~~~^~~~~~~
reconstruction.cpp:52:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |  scanf("%d%d", &N, &M);
      |  ~~~~~^~~~~~~~~~~~~~~~
reconstruction.cpp:56:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |   scanf("%d%d%lld", &u, &v, &w); w*=2;
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
reconstruction.cpp:60:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |  scanf("%d", &Q);
      |  ~~~~~^~~~~~~~~~
reconstruction.cpp:61:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |  for(int i=1; i<=Q; i++) scanf("%d", &B[i]), B[i]*=2;
      |                          ~~~~~^~~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 316 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 312 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 308 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 312 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 340 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 316 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 312 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 308 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 312 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 308 KB Output is correct
20 Correct 3868 ms 16964 KB Output is correct
21 Correct 2790 ms 16980 KB Output is correct
22 Correct 2837 ms 16968 KB Output is correct
23 Correct 3060 ms 16964 KB Output is correct
24 Correct 3468 ms 16972 KB Output is correct
25 Correct 3692 ms 16972 KB Output is correct
26 Correct 3752 ms 17032 KB Output is correct
27 Correct 3754 ms 16204 KB Output is correct
28 Correct 3709 ms 4556 KB Output is correct
29 Correct 3696 ms 4432 KB Output is correct
30 Correct 3753 ms 16972 KB Output is correct
31 Correct 3737 ms 16972 KB Output is correct
32 Correct 3775 ms 16956 KB Output is correct
33 Correct 3904 ms 16972 KB Output is correct
34 Correct 3905 ms 4528 KB Output is correct
35 Correct 4083 ms 16968 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 3660 ms 87540 KB Output is correct
5 Correct 3553 ms 88068 KB Output is correct
6 Correct 3452 ms 88068 KB Output is correct
7 Correct 2024 ms 89980 KB Output is correct
8 Correct 1783 ms 90024 KB Output is correct
9 Correct 1727 ms 90124 KB Output is correct
10 Correct 3435 ms 96460 KB Output is correct
11 Correct 1813 ms 98428 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 316 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 312 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 308 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 312 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 580 ms 82476 KB Output is correct
21 Correct 580 ms 82840 KB Output is correct
22 Correct 599 ms 82764 KB Output is correct
23 Correct 585 ms 82740 KB Output is correct
24 Correct 585 ms 82672 KB Output is correct
25 Correct 573 ms 82648 KB Output is correct
26 Correct 570 ms 82380 KB Output is correct
27 Correct 573 ms 82380 KB Output is correct
28 Correct 582 ms 82532 KB Output is correct
29 Correct 580 ms 82412 KB Output is correct
30 Correct 576 ms 82384 KB Output is correct
31 Correct 579 ms 82384 KB Output is correct
32 Correct 580 ms 82692 KB Output is correct
33 Correct 581 ms 82000 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 316 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 312 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 308 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 312 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 308 KB Output is correct
20 Correct 3868 ms 16964 KB Output is correct
21 Correct 2790 ms 16980 KB Output is correct
22 Correct 2837 ms 16968 KB Output is correct
23 Correct 3060 ms 16964 KB Output is correct
24 Correct 3468 ms 16972 KB Output is correct
25 Correct 3692 ms 16972 KB Output is correct
26 Correct 3752 ms 17032 KB Output is correct
27 Correct 3754 ms 16204 KB Output is correct
28 Correct 3709 ms 4556 KB Output is correct
29 Correct 3696 ms 4432 KB Output is correct
30 Correct 3753 ms 16972 KB Output is correct
31 Correct 3737 ms 16972 KB Output is correct
32 Correct 3775 ms 16956 KB Output is correct
33 Correct 3904 ms 16972 KB Output is correct
34 Correct 3905 ms 4528 KB Output is correct
35 Correct 4083 ms 16968 KB Output is correct
36 Correct 3755 ms 17832 KB Output is correct
37 Correct 2705 ms 17784 KB Output is correct
38 Correct 2826 ms 17752 KB Output is correct
39 Correct 2988 ms 17748 KB Output is correct
40 Correct 3340 ms 17752 KB Output is correct
41 Correct 3839 ms 17868 KB Output is correct
42 Correct 3833 ms 17748 KB Output is correct
43 Correct 3851 ms 17184 KB Output is correct
44 Correct 3753 ms 5560 KB Output is correct
45 Correct 3765 ms 5440 KB Output is correct
46 Correct 3801 ms 17960 KB Output is correct
47 Correct 3820 ms 17996 KB Output is correct
48 Correct 3780 ms 17956 KB Output is correct
49 Correct 3771 ms 17964 KB Output is correct
50 Correct 3731 ms 5640 KB Output is correct
51 Correct 3747 ms 17960 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 316 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 312 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 308 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 312 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 308 KB Output is correct
20 Correct 3868 ms 16964 KB Output is correct
21 Correct 2790 ms 16980 KB Output is correct
22 Correct 2837 ms 16968 KB Output is correct
23 Correct 3060 ms 16964 KB Output is correct
24 Correct 3468 ms 16972 KB Output is correct
25 Correct 3692 ms 16972 KB Output is correct
26 Correct 3752 ms 17032 KB Output is correct
27 Correct 3754 ms 16204 KB Output is correct
28 Correct 3709 ms 4556 KB Output is correct
29 Correct 3696 ms 4432 KB Output is correct
30 Correct 3753 ms 16972 KB Output is correct
31 Correct 3737 ms 16972 KB Output is correct
32 Correct 3775 ms 16956 KB Output is correct
33 Correct 3904 ms 16972 KB Output is correct
34 Correct 3905 ms 4528 KB Output is correct
35 Correct 4083 ms 16968 KB Output is correct
36 Correct 1 ms 212 KB Output is correct
37 Correct 1 ms 212 KB Output is correct
38 Correct 1 ms 340 KB Output is correct
39 Correct 3660 ms 87540 KB Output is correct
40 Correct 3553 ms 88068 KB Output is correct
41 Correct 3452 ms 88068 KB Output is correct
42 Correct 2024 ms 89980 KB Output is correct
43 Correct 1783 ms 90024 KB Output is correct
44 Correct 1727 ms 90124 KB Output is correct
45 Correct 3435 ms 96460 KB Output is correct
46 Correct 1813 ms 98428 KB Output is correct
47 Correct 1 ms 340 KB Output is correct
48 Correct 580 ms 82476 KB Output is correct
49 Correct 580 ms 82840 KB Output is correct
50 Correct 599 ms 82764 KB Output is correct
51 Correct 585 ms 82740 KB Output is correct
52 Correct 585 ms 82672 KB Output is correct
53 Correct 573 ms 82648 KB Output is correct
54 Correct 570 ms 82380 KB Output is correct
55 Correct 573 ms 82380 KB Output is correct
56 Correct 582 ms 82532 KB Output is correct
57 Correct 580 ms 82412 KB Output is correct
58 Correct 576 ms 82384 KB Output is correct
59 Correct 579 ms 82384 KB Output is correct
60 Correct 580 ms 82692 KB Output is correct
61 Correct 581 ms 82000 KB Output is correct
62 Correct 3755 ms 17832 KB Output is correct
63 Correct 2705 ms 17784 KB Output is correct
64 Correct 2826 ms 17752 KB Output is correct
65 Correct 2988 ms 17748 KB Output is correct
66 Correct 3340 ms 17752 KB Output is correct
67 Correct 3839 ms 17868 KB Output is correct
68 Correct 3833 ms 17748 KB Output is correct
69 Correct 3851 ms 17184 KB Output is correct
70 Correct 3753 ms 5560 KB Output is correct
71 Correct 3765 ms 5440 KB Output is correct
72 Correct 3801 ms 17960 KB Output is correct
73 Correct 3820 ms 17996 KB Output is correct
74 Correct 3780 ms 17956 KB Output is correct
75 Correct 3771 ms 17964 KB Output is correct
76 Correct 3731 ms 5640 KB Output is correct
77 Correct 3747 ms 17960 KB Output is correct
78 Correct 4323 ms 86572 KB Output is correct
79 Correct 3232 ms 88572 KB Output is correct
80 Correct 3377 ms 87544 KB Output is correct
81 Correct 3526 ms 87552 KB Output is correct
82 Correct 3936 ms 86524 KB Output is correct
83 Correct 4244 ms 86296 KB Output is correct
84 Correct 4356 ms 86376 KB Output is correct
85 Correct 4398 ms 85820 KB Output is correct
86 Correct 4289 ms 81696 KB Output is correct
87 Correct 4267 ms 83072 KB Output is correct
88 Correct 4358 ms 94008 KB Output is correct
89 Correct 4417 ms 94052 KB Output is correct
90 Correct 4421 ms 93704 KB Output is correct
91 Correct 4646 ms 92800 KB Output is correct
92 Correct 4619 ms 84640 KB Output is correct
93 Correct 4619 ms 95352 KB Output is correct