oj.uz

Submission #547376

# Submission time Handle Problem Language Result Execution time Memory
547376 2022-04-10T14:27:20 Z blue Reconstruction Project (JOI22_reconstruction) C++17
100 / 100
 3472 ms 35132 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <cassert>
using namespace std;

using ll = long long;
using vll = vector<ll>;
using vi = vector<int>;
using vvi = vector<vi>;
using pll = pair<ll, ll>;
#define sz(x) int(x.size())

struct edge
{
	int a;
	int b;
	ll w;
};

bool operator < (edge A, edge B)
{
	return A.w < B.w;
}

struct costchange
{
	ll w;
	ll deltaX;
	ll deltaC;
};

bool operator < (costchange A, costchange B)
{
	return A.w < B.w;
}



const int maxM = 100'000;
const int maxN = 500;

vi A(maxM), B(maxM), W(maxM);




set<int> adj[maxN];

void addedge(int e)
{
	adj[A[e]].insert(e);
	adj[B[e]].insert(e);
}

void removeedge(int e)
{
	adj[A[e]].erase(e);
	adj[B[e]].erase(e);
}

vi vis; //done
vi cyclic; //done

vi st; //done

vi paredge;

bool discovered;

void dfs(int u, int pe)
{
	// cerr << "\n\n\n\n";
	// cerr << "enter : dfs " << u << ' ' << p << '\n';
	vis[u] = 1;

	st.push_back(u);
	for(int e : adj[u])
	{
		// cerr << "enter edge\n";
		int v = A[e] + B[e] - u;

		// cerr << u << " -> " << v << '\n';
		if(e == pe) 
		{
			// cerr << "case 1\n";
			continue;
		}
		else if(vis[v])
		{
			if(!discovered)
			{
				discovered = 1;
				// cerr << "case 2\n";

				// cerr << "paredge v = " << paredge[v] << '\n';
				// for(int f : st) cerr << "f = " << f << " : " << paredge[f] << '\n';

				for(int k = sz(st) - 1; k >= 0 && st[k] != v; k--)
				{
					// cerr << "checking : k = " << k << '\n';
					// if(paredge[st[k]] == -1) cerr << "ATTENTION : V = " << v << '\n'; 
					cyclic.push_back(paredge[st[k]]);
				}
				cyclic.push_back(e);
				// cerr << "case 2 done\n";
			}
			
		}
		else
		{
			// cerr << "case 3\n";
			paredge[v] = e;
			dfs(v, e);
			if(discovered) return;
		}

	}
	st.pop_back();
}








int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int N, M;
	cin >> N >> M;

	// assert(M*N <= 50'000'000 - 1);

	vector<edge> E(M);
	for(int j = 0; j < M; j++)
	{
		cin >> E[j].a >> E[j].b >> E[j].w;
		E[j].a--;
		E[j].b--;
	}
	sort(E.begin(), E.end());

	for(int j = 0; j < M; j++)
	{
		A[j] = E[j].a;
		B[j] = E[j].b;
		W[j] = E[j].w;
	}

	// cerr << "\n\n\n edges = \n";
	// for(int j = 0; j < M; j++) cerr << A[j] << ' ' << B[j] << ' ' << W[j] << '\n';
	// 	cerr << "\n\n";



	for(int i = 0; i < N; i++)
		adj[i].clear();

	vi edgelist;


	vll minW(M), maxW(M); //do 2x the actual thing!!!

	for(int j = 0; j < M; j++)
	{
		// cerr << "\n\n\n\n\n\n\n";
		// cerr << "j = " << j << '\n';
		vis = vi(N, 0);
		assert(sz(edgelist) < N);

		// edgelist.push_back(j);
		addedge(j);


		// cerr << "edgelist : \n";
		// for(int e : edgelist)
		// 	cerr << A[e] << ' ' << B[e] << ' ' << W[e] << '\n';

		// cerr << "###\n";
		// adj = vvi(N);
		// for(int e : edgelist)
		// {
		// 	adj[A[e]].push_back(e);
		// 	adj[B[e]].push_back(e);
		// }

		cyclic.clear();

		discovered = 0;

		st.clear();

		paredge = vi(N, -1);

		// cerr << "done\n";

		for(int i = 0; i < N; i++)
		{
			if(vis[i]) continue;
			if(discovered) break;
			dfs(i, -1);
		}

		// cerr << "dfs done\n";

		if(cyclic.empty()) minW[j] = 0;
		else
		{
			// cerr << "!!!!!CYCLIC DETECTED!!!!!\n";
			// cerr << "case = 2" << '\n';

			int mincyclic = cyclic[0];
			for(int c : cyclic)
				mincyclic = min(mincyclic, c);

			removeedge(mincyclic);
			// cerr << "# done\n";

			// cerr << "mincyclic = " << mincyclic << '\n';

			minW[j] = W[j] + W[mincyclic];

			// cerr << "transition from " << mincyclic << " to " << j << " = " << minW[j] << "/2" << '\n';

			// cerr << "3 done\n";
		}

		// cerr << "J = " << j << " done\n";
	}






























	// cerr << "check\n";
	// cerr << "\n\n\n\n\n\n\n\nPART 2 PART 2 PART 2\n";


	// edgelist.clear();

	for(int i = 0; i < N; i++)
		adj[i].clear();

	for(int j = M-1; j >= 0; j--)
	{
		// cerr << "\n\n\n\n\n\n\n";
		// cerr << "j = " << j << '\n';
		vis = vi(N, 0);
		assert(sz(edgelist) < N);

		// edgelist.push_back(j);
		addedge(j);

		// cerr << "edgelist : \n";
		// for(int e : edgelist)
		// 	cerr << A[e] << ' ' << B[e] << ' ' << W[e] << '\n';

		// cerr << "###\n";
		// adj = vvi(N);
		// for(int e : edgelist)
		// {
		// 	adj[A[e]].push_back(e);
		// 	adj[B[e]].push_back(e);
		// }

		cyclic.clear();

		discovered = 0;

		st.clear();

		paredge = vi(N, -1);

		// cerr << "done\n";

		for(int i = 0; i < N; i++)
		{
			if(vis[i]) continue;
			if(discovered) break;
			dfs(i, -1);
		}

		// cerr << "dfs done\n";

		if(cyclic.empty()) maxW[j] = 2'000'000'004;
		else
		{
			// cerr << "!!!!!CYCLIC DETECTED!!!!!\n";
			// cerr << "case = 2" << '\n';
			// vi nwedgelist;

			int maxcyclic = cyclic[0];
			for(int c : cyclic)
				maxcyclic = max(maxcyclic, c);

			// cerr << "1 done\n";

			// for(int e : edgelist)
			// 	if(e != maxcyclic)
			// 		nwedgelist.push_back(e);
			removeedge(maxcyclic);

			// cerr << "2 done\n";

			// edgelist = nwedgelist;

			// cerr << "# done\n";

			maxW[j] = W[j] + W[maxcyclic];

			// cerr << "3 done\n";
		}

		// cerr << "J = " << j << " done\n";
	}


	// for(int j = 0; j < M; j++) cerr << A[j] << ' ' << B[j] << ' ' << W[j] << " : " << minW[j] << ' ' << maxW[j] << '\n';


	vector<pll> deltaX, deltaC;

	for(int j = 0; j < M; j++)
	{
		deltaX.push_back({minW[j], -1});
		deltaC.push_back({minW[j], W[j]});

		deltaX.push_back({2*W[j], +1});
		deltaC.push_back({2*W[j], -W[j]});

		deltaX.push_back({2*W[j]+1, +1});
		deltaC.push_back({2*W[j]+1, -W[j]});

		deltaX.push_back({maxW[j], -1});
		deltaC.push_back({maxW[j], +W[j]});
	}

	sort(deltaX.begin(), deltaX.end());
	sort(deltaC.begin(), deltaC.end());


	ll currX = 0, currC = 0;

	int it = -1;

	int Q;
	cin >> Q;

	for(int q = 0; q < Q; q++)
	{
		ll X;
		cin >> X;

		while(it+1 < sz(deltaX) && deltaX[it+1].first <= 2*X)
		{
			it++;
			currX += deltaX[it].second;
			currC += deltaC[it].second;
		}

		cout << currX*X + currC << '\n';
	}
}

Subtask #1
3.0 / 3.0

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

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1492 KB Output is correct
2 Correct 1 ms 1492 KB Output is correct
3 Correct 1 ms 1492 KB Output is correct
4 Correct 1 ms 1492 KB Output is correct
5 Correct 1 ms 1492 KB Output is correct
6 Correct 1 ms 1492 KB Output is correct
7 Correct 1 ms 1492 KB Output is correct
8 Correct 1 ms 1492 KB Output is correct
9 Correct 1 ms 1492 KB Output is correct
10 Correct 2 ms 1492 KB Output is correct
11 Correct 1 ms 1492 KB Output is correct
12 Correct 1 ms 1492 KB Output is correct
13 Correct 1 ms 1492 KB Output is correct
14 Correct 2 ms 1492 KB Output is correct
15 Correct 1 ms 1492 KB Output is correct
16 Correct 1 ms 1436 KB Output is correct
17 Correct 1 ms 1492 KB Output is correct
18 Correct 1 ms 1492 KB Output is correct
19 Correct 1 ms 1492 KB Output is correct
20 Correct 2033 ms 17388 KB Output is correct
21 Correct 1980 ms 17388 KB Output is correct
22 Correct 2001 ms 17388 KB Output is correct
23 Correct 2017 ms 17392 KB Output is correct
24 Correct 2004 ms 17492 KB Output is correct
25 Correct 1948 ms 17388 KB Output is correct
26 Correct 1996 ms 17392 KB Output is correct
27 Correct 1970 ms 17432 KB Output is correct
28 Correct 1992 ms 17396 KB Output is correct
29 Correct 1972 ms 17388 KB Output is correct
30 Correct 2005 ms 17392 KB Output is correct
31 Correct 2013 ms 17388 KB Output is correct
32 Correct 2000 ms 17392 KB Output is correct
33 Correct 2016 ms 17392 KB Output is correct
34 Correct 1969 ms 17388 KB Output is correct
35 Correct 2040 ms 17332 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1492 KB Output is correct
2 Correct 1 ms 1492 KB Output is correct
3 Correct 1 ms 1492 KB Output is correct
4 Correct 3472 ms 32568 KB Output is correct
5 Correct 3433 ms 33048 KB Output is correct
6 Correct 3383 ms 33124 KB Output is correct
7 Correct 1598 ms 34964 KB Output is correct
8 Correct 1553 ms 35132 KB Output is correct
9 Correct 1254 ms 35096 KB Output is correct
10 Correct 3433 ms 33212 KB Output is correct
11 Correct 1454 ms 34992 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1492 KB Output is correct
2 Correct 1 ms 1492 KB Output is correct
3 Correct 1 ms 1492 KB Output is correct
4 Correct 1 ms 1492 KB Output is correct
5 Correct 1 ms 1492 KB Output is correct
6 Correct 1 ms 1492 KB Output is correct
7 Correct 1 ms 1492 KB Output is correct
8 Correct 1 ms 1492 KB Output is correct
9 Correct 1 ms 1492 KB Output is correct
10 Correct 2 ms 1492 KB Output is correct
11 Correct 1 ms 1492 KB Output is correct
12 Correct 1 ms 1492 KB Output is correct
13 Correct 1 ms 1492 KB Output is correct
14 Correct 2 ms 1492 KB Output is correct
15 Correct 1 ms 1492 KB Output is correct
16 Correct 1 ms 1436 KB Output is correct
17 Correct 1 ms 1492 KB Output is correct
18 Correct 1 ms 1492 KB Output is correct
19 Correct 1 ms 1492 KB Output is correct
20 Correct 215 ms 14048 KB Output is correct
21 Correct 206 ms 14124 KB Output is correct
22 Correct 203 ms 14192 KB Output is correct
23 Correct 199 ms 14072 KB Output is correct
24 Correct 205 ms 14156 KB Output is correct
25 Correct 207 ms 14064 KB Output is correct
26 Correct 216 ms 13992 KB Output is correct
27 Correct 221 ms 14040 KB Output is correct
28 Correct 219 ms 13960 KB Output is correct
29 Correct 217 ms 14108 KB Output is correct
30 Correct 205 ms 14024 KB Output is correct
31 Correct 206 ms 14000 KB Output is correct
32 Correct 210 ms 14560 KB Output is correct
33 Correct 211 ms 13872 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1492 KB Output is correct
2 Correct 1 ms 1492 KB Output is correct
3 Correct 1 ms 1492 KB Output is correct
4 Correct 1 ms 1492 KB Output is correct
5 Correct 1 ms 1492 KB Output is correct
6 Correct 1 ms 1492 KB Output is correct
7 Correct 1 ms 1492 KB Output is correct
8 Correct 1 ms 1492 KB Output is correct
9 Correct 1 ms 1492 KB Output is correct
10 Correct 2 ms 1492 KB Output is correct
11 Correct 1 ms 1492 KB Output is correct
12 Correct 1 ms 1492 KB Output is correct
13 Correct 1 ms 1492 KB Output is correct
14 Correct 2 ms 1492 KB Output is correct
15 Correct 1 ms 1492 KB Output is correct
16 Correct 1 ms 1436 KB Output is correct
17 Correct 1 ms 1492 KB Output is correct
18 Correct 1 ms 1492 KB Output is correct
19 Correct 1 ms 1492 KB Output is correct
20 Correct 2033 ms 17388 KB Output is correct
21 Correct 1980 ms 17388 KB Output is correct
22 Correct 2001 ms 17388 KB Output is correct
23 Correct 2017 ms 17392 KB Output is correct
24 Correct 2004 ms 17492 KB Output is correct
25 Correct 1948 ms 17388 KB Output is correct
26 Correct 1996 ms 17392 KB Output is correct
27 Correct 1970 ms 17432 KB Output is correct
28 Correct 1992 ms 17396 KB Output is correct
29 Correct 1972 ms 17388 KB Output is correct
30 Correct 2005 ms 17392 KB Output is correct
31 Correct 2013 ms 17388 KB Output is correct
32 Correct 2000 ms 17392 KB Output is correct
33 Correct 2016 ms 17392 KB Output is correct
34 Correct 1969 ms 17388 KB Output is correct
35 Correct 2040 ms 17332 KB Output is correct
36 Correct 2043 ms 17496 KB Output is correct
37 Correct 1951 ms 17628 KB Output is correct
38 Correct 2029 ms 17500 KB Output is correct
39 Correct 2001 ms 17496 KB Output is correct
40 Correct 1977 ms 17508 KB Output is correct
41 Correct 1873 ms 17624 KB Output is correct
42 Correct 1943 ms 17524 KB Output is correct
43 Correct 1920 ms 17584 KB Output is correct
44 Correct 1913 ms 17536 KB Output is correct
45 Correct 1949 ms 17492 KB Output is correct
46 Correct 1919 ms 17500 KB Output is correct
47 Correct 1930 ms 17492 KB Output is correct
48 Correct 1971 ms 17508 KB Output is correct
49 Correct 1946 ms 17648 KB Output is correct
50 Correct 1913 ms 17764 KB Output is correct
51 Correct 1912 ms 17516 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1492 KB Output is correct
2 Correct 1 ms 1492 KB Output is correct
3 Correct 1 ms 1492 KB Output is correct
4 Correct 1 ms 1492 KB Output is correct
5 Correct 1 ms 1492 KB Output is correct
6 Correct 1 ms 1492 KB Output is correct
7 Correct 1 ms 1492 KB Output is correct
8 Correct 1 ms 1492 KB Output is correct
9 Correct 1 ms 1492 KB Output is correct
10 Correct 2 ms 1492 KB Output is correct
11 Correct 1 ms 1492 KB Output is correct
12 Correct 1 ms 1492 KB Output is correct
13 Correct 1 ms 1492 KB Output is correct
14 Correct 2 ms 1492 KB Output is correct
15 Correct 1 ms 1492 KB Output is correct
16 Correct 1 ms 1436 KB Output is correct
17 Correct 1 ms 1492 KB Output is correct
18 Correct 1 ms 1492 KB Output is correct
19 Correct 1 ms 1492 KB Output is correct
20 Correct 2033 ms 17388 KB Output is correct
21 Correct 1980 ms 17388 KB Output is correct
22 Correct 2001 ms 17388 KB Output is correct
23 Correct 2017 ms 17392 KB Output is correct
24 Correct 2004 ms 17492 KB Output is correct
25 Correct 1948 ms 17388 KB Output is correct
26 Correct 1996 ms 17392 KB Output is correct
27 Correct 1970 ms 17432 KB Output is correct
28 Correct 1992 ms 17396 KB Output is correct
29 Correct 1972 ms 17388 KB Output is correct
30 Correct 2005 ms 17392 KB Output is correct
31 Correct 2013 ms 17388 KB Output is correct
32 Correct 2000 ms 17392 KB Output is correct
33 Correct 2016 ms 17392 KB Output is correct
34 Correct 1969 ms 17388 KB Output is correct
35 Correct 2040 ms 17332 KB Output is correct
36 Correct 1 ms 1492 KB Output is correct
37 Correct 1 ms 1492 KB Output is correct
38 Correct 1 ms 1492 KB Output is correct
39 Correct 3472 ms 32568 KB Output is correct
40 Correct 3433 ms 33048 KB Output is correct
41 Correct 3383 ms 33124 KB Output is correct
42 Correct 1598 ms 34964 KB Output is correct
43 Correct 1553 ms 35132 KB Output is correct
44 Correct 1254 ms 35096 KB Output is correct
45 Correct 3433 ms 33212 KB Output is correct
46 Correct 1454 ms 34992 KB Output is correct
47 Correct 1 ms 1492 KB Output is correct
48 Correct 215 ms 14048 KB Output is correct
49 Correct 206 ms 14124 KB Output is correct
50 Correct 203 ms 14192 KB Output is correct
51 Correct 199 ms 14072 KB Output is correct
52 Correct 205 ms 14156 KB Output is correct
53 Correct 207 ms 14064 KB Output is correct
54 Correct 216 ms 13992 KB Output is correct
55 Correct 221 ms 14040 KB Output is correct
56 Correct 219 ms 13960 KB Output is correct
57 Correct 217 ms 14108 KB Output is correct
58 Correct 205 ms 14024 KB Output is correct
59 Correct 206 ms 14000 KB Output is correct
60 Correct 210 ms 14560 KB Output is correct
61 Correct 211 ms 13872 KB Output is correct
62 Correct 2043 ms 17496 KB Output is correct
63 Correct 1951 ms 17628 KB Output is correct
64 Correct 2029 ms 17500 KB Output is correct
65 Correct 2001 ms 17496 KB Output is correct
66 Correct 1977 ms 17508 KB Output is correct
67 Correct 1873 ms 17624 KB Output is correct
68 Correct 1943 ms 17524 KB Output is correct
69 Correct 1920 ms 17584 KB Output is correct
70 Correct 1913 ms 17536 KB Output is correct
71 Correct 1949 ms 17492 KB Output is correct
72 Correct 1919 ms 17500 KB Output is correct
73 Correct 1930 ms 17492 KB Output is correct
74 Correct 1971 ms 17508 KB Output is correct
75 Correct 1946 ms 17648 KB Output is correct
76 Correct 1913 ms 17764 KB Output is correct
77 Correct 1912 ms 17516 KB Output is correct
78 Correct 2126 ms 27536 KB Output is correct
79 Correct 2032 ms 29392 KB Output is correct
80 Correct 2121 ms 28500 KB Output is correct
81 Correct 2134 ms 28488 KB Output is correct
82 Correct 2095 ms 27484 KB Output is correct
83 Correct 2095 ms 27436 KB Output is correct
84 Correct 2100 ms 27348 KB Output is correct
85 Correct 2118 ms 27424 KB Output is correct
86 Correct 2095 ms 27480 KB Output is correct
87 Correct 2066 ms 29136 KB Output is correct
88 Correct 2091 ms 27588 KB Output is correct
89 Correct 2155 ms 27352 KB Output is correct
90 Correct 2126 ms 27496 KB Output is correct
91 Correct 2073 ms 27356 KB Output is correct
92 Correct 2096 ms 30320 KB Output is correct
93 Correct 2103 ms 28380 KB Output is correct