oj.uz

Submission #681151

# Submission time Handle Problem Language Result Execution time Memory
681151 2023-01-12T12:30:55 Z arnold518 Reconstruction Project (JOI22_reconstruction) C++17
42 / 100
 5000 ms 215308 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 int INF = 1e9+7;

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

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

vector<int> V[MAXM+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 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 main()
{
	scanf("%d%d", &N, &M);
	for(int i=1; i<=M; i++)
	{
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		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].first), B[i].second=i;
	sort(B+1, B+Q+1);

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

	vector<int> V2;
	for(int i=1, j=1; i<=M+1; i++)
	{
		for(; j<=Q && B[j].first<=A[i].w; j++)
		{
			uf.init();
			int l=0, r=0;
			while(l<V2.size() || r<V[i].size())
			{
				int it;
				if(l<V2.size() && (r==V[i].size() || B[j].first-A[V2[l]].w<A[V[i][r]].w-B[j].first)) it=V2[l++];
				else it=V[i][r++];

				if(uf.Find(A[it].u)==uf.Find(A[it].v)) continue;
				uf.Union(A[it].u, A[it].v);
				ans[B[j].second]+=abs(A[it].w-B[j].first);
			}
		}

		if(i>M) break;

		vector<int> VV;

		uf.init();
		uf.Union(A[i].u, A[i].v);
		VV.push_back(i);
		for(auto it : V2)
		{
			if(uf.Find(A[it].u)==uf.Find(A[it].v)) continue;
			uf.Union(A[it].u, A[it].v);
			VV.push_back(it);
		}
		V2=VV;
	}
	for(int i=1; i<=Q; i++) printf("%lld\n", ans[i]);

}

Compilation message

reconstruction.cpp: In function 'int main()':
reconstruction.cpp:84:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |    while(l<V2.size() || r<V[i].size())
      |          ~^~~~~~~~~~
reconstruction.cpp:84:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |    while(l<V2.size() || r<V[i].size())
      |                         ~^~~~~~~~~~~~
reconstruction.cpp:87:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |     if(l<V2.size() && (r==V[i].size() || B[j].first-A[V2[l]].w<A[V[i][r]].w-B[j].first)) it=V2[l++];
      |        ~^~~~~~~~~~
reconstruction.cpp:87:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |     if(l<V2.size() && (r==V[i].size() || B[j].first-A[V2[l]].w<A[V[i][r]].w-B[j].first)) it=V2[l++];
      |                        ~^~~~~~~~~~~~~
reconstruction.cpp:50:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |  scanf("%d%d", &N, &M);
      |  ~~~~~^~~~~~~~~~~~~~~~
reconstruction.cpp:54:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |   scanf("%d%d%d", &u, &v, &w);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
reconstruction.cpp:58:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |  scanf("%d", &Q);
      |  ~~~~~^~~~~~~~~~
reconstruction.cpp:59:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |  for(int i=1; i<=Q; i++) scanf("%d", &B[i].first), B[i].second=i;
      |                          ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 1 ms 2660 KB Output is correct
4 Correct 1 ms 2668 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 2 ms 2668 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 1 ms 2664 KB Output is correct
9 Correct 1 ms 2644 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 2 ms 2644 KB Output is correct
13 Correct 2 ms 2644 KB Output is correct
14 Correct 1 ms 2644 KB Output is correct
15 Correct 2 ms 2668 KB Output is correct
16 Correct 2 ms 2644 KB Output is correct
17 Correct 2 ms 2644 KB Output is correct
18 Correct 2 ms 2668 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 1 ms 2660 KB Output is correct
4 Correct 1 ms 2668 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 2 ms 2668 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 1 ms 2664 KB Output is correct
9 Correct 1 ms 2644 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 2 ms 2644 KB Output is correct
13 Correct 2 ms 2644 KB Output is correct
14 Correct 1 ms 2644 KB Output is correct
15 Correct 2 ms 2668 KB Output is correct
16 Correct 2 ms 2644 KB Output is correct
17 Correct 2 ms 2644 KB Output is correct
18 Correct 2 ms 2668 KB Output is correct
19 Correct 1 ms 2644 KB Output is correct
20 Correct 2009 ms 206656 KB Output is correct
21 Correct 1568 ms 206060 KB Output is correct
22 Correct 1669 ms 205908 KB Output is correct
23 Correct 1646 ms 206080 KB Output is correct
24 Correct 1783 ms 206032 KB Output is correct
25 Correct 1953 ms 206120 KB Output is correct
26 Correct 1937 ms 206048 KB Output is correct
27 Correct 1922 ms 206112 KB Output is correct
28 Correct 1918 ms 206156 KB Output is correct
29 Correct 1916 ms 205920 KB Output is correct
30 Correct 1926 ms 206024 KB Output is correct
31 Correct 1955 ms 206020 KB Output is correct
32 Correct 1927 ms 206236 KB Output is correct
33 Correct 1934 ms 206228 KB Output is correct
34 Correct 1920 ms 206248 KB Output is correct
35 Correct 1960 ms 206260 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Execution timed out 5088 ms 215308 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 1 ms 2660 KB Output is correct
4 Correct 1 ms 2668 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 2 ms 2668 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 1 ms 2664 KB Output is correct
9 Correct 1 ms 2644 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 2 ms 2644 KB Output is correct
13 Correct 2 ms 2644 KB Output is correct
14 Correct 1 ms 2644 KB Output is correct
15 Correct 2 ms 2668 KB Output is correct
16 Correct 2 ms 2644 KB Output is correct
17 Correct 2 ms 2644 KB Output is correct
18 Correct 2 ms 2668 KB Output is correct
19 Correct 2 ms 2644 KB Output is correct
20 Execution timed out 5034 ms 16816 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 1 ms 2660 KB Output is correct
4 Correct 1 ms 2668 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 2 ms 2668 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 1 ms 2664 KB Output is correct
9 Correct 1 ms 2644 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 2 ms 2644 KB Output is correct
13 Correct 2 ms 2644 KB Output is correct
14 Correct 1 ms 2644 KB Output is correct
15 Correct 2 ms 2668 KB Output is correct
16 Correct 2 ms 2644 KB Output is correct
17 Correct 2 ms 2644 KB Output is correct
18 Correct 2 ms 2668 KB Output is correct
19 Correct 1 ms 2644 KB Output is correct
20 Correct 2009 ms 206656 KB Output is correct
21 Correct 1568 ms 206060 KB Output is correct
22 Correct 1669 ms 205908 KB Output is correct
23 Correct 1646 ms 206080 KB Output is correct
24 Correct 1783 ms 206032 KB Output is correct
25 Correct 1953 ms 206120 KB Output is correct
26 Correct 1937 ms 206048 KB Output is correct
27 Correct 1922 ms 206112 KB Output is correct
28 Correct 1918 ms 206156 KB Output is correct
29 Correct 1916 ms 205920 KB Output is correct
30 Correct 1926 ms 206024 KB Output is correct
31 Correct 1955 ms 206020 KB Output is correct
32 Correct 1927 ms 206236 KB Output is correct
33 Correct 1934 ms 206228 KB Output is correct
34 Correct 1920 ms 206248 KB Output is correct
35 Correct 1960 ms 206260 KB Output is correct
36 Correct 2636 ms 206724 KB Output is correct
37 Correct 2102 ms 206640 KB Output is correct
38 Correct 2199 ms 206568 KB Output is correct
39 Correct 2317 ms 206552 KB Output is correct
40 Correct 2464 ms 206576 KB Output is correct
41 Correct 2661 ms 206664 KB Output is correct
42 Correct 2646 ms 206568 KB Output is correct
43 Correct 2646 ms 206704 KB Output is correct
44 Correct 2410 ms 206576 KB Output is correct
45 Correct 2189 ms 206452 KB Output is correct
46 Correct 2640 ms 206680 KB Output is correct
47 Correct 2624 ms 206488 KB Output is correct
48 Correct 2599 ms 206736 KB Output is correct
49 Correct 2602 ms 206484 KB Output is correct
50 Correct 2065 ms 206588 KB Output is correct
51 Correct 2222 ms 206464 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 1 ms 2660 KB Output is correct
4 Correct 1 ms 2668 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 2 ms 2668 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 1 ms 2664 KB Output is correct
9 Correct 1 ms 2644 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 2 ms 2644 KB Output is correct
13 Correct 2 ms 2644 KB Output is correct
14 Correct 1 ms 2644 KB Output is correct
15 Correct 2 ms 2668 KB Output is correct
16 Correct 2 ms 2644 KB Output is correct
17 Correct 2 ms 2644 KB Output is correct
18 Correct 2 ms 2668 KB Output is correct
19 Correct 1 ms 2644 KB Output is correct
20 Correct 2009 ms 206656 KB Output is correct
21 Correct 1568 ms 206060 KB Output is correct
22 Correct 1669 ms 205908 KB Output is correct
23 Correct 1646 ms 206080 KB Output is correct
24 Correct 1783 ms 206032 KB Output is correct
25 Correct 1953 ms 206120 KB Output is correct
26 Correct 1937 ms 206048 KB Output is correct
27 Correct 1922 ms 206112 KB Output is correct
28 Correct 1918 ms 206156 KB Output is correct
29 Correct 1916 ms 205920 KB Output is correct
30 Correct 1926 ms 206024 KB Output is correct
31 Correct 1955 ms 206020 KB Output is correct
32 Correct 1927 ms 206236 KB Output is correct
33 Correct 1934 ms 206228 KB Output is correct
34 Correct 1920 ms 206248 KB Output is correct
35 Correct 1960 ms 206260 KB Output is correct
36 Correct 3 ms 2644 KB Output is correct
37 Correct 2 ms 2644 KB Output is correct
38 Correct 1 ms 2644 KB Output is correct
39 Execution timed out 5088 ms 215308 KB Time limit exceeded
40 Halted 0 ms 0 KB -