제출 #681181

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
681181		arnold518	Reconstruction Project (JOI22_reconstruction)	C++17	100 / 100	4646 ms	98428 KiB

reconstruction

#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);
	}
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 3
• Subtask 2: 4 / 4
• Subtask 3: 7 / 7
• Subtask 4: 28 / 28
• Subtask 5: 35 / 35
• Subtask 6: 23 / 23