Submission #617443

#	Time	Username	Problem	Language	Result	Execution time	Memory
617443		patrikpavic2	Reconstruction Project (JOI22_reconstruction)	C++17	100 / 100	992 ms	63028 KiB

reconstruction

#include <cstdio>
#include <vector>
#include <algorithm>

#define X first
#define Y second
#define PB push_back

using namespace std;

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

const int N = 1e6 + 500;
const int NN = 505;
const int INF = 0x3f3f3f3f;

vector < pip > edg;
vector < pii > v[NN];

int kofa = 0, n, m, q;
int bar[N], gor[N], qq[N];
ll odg1[N], odg2[N], cnt1[N], cnt2[N];

int miin(int A, int B){
	if(!kofa) return (edg[A].X <= edg[B].X ? A : B);
	else 	  return (edg[A].X > edg[B].X ? A : B);
}

int get_path(int cur, int lst, int krj){
	if(cur == krj) return m;
	for(pii tmp : v[cur]){
		if(tmp.X == lst) continue;
		int rt = get_path(tmp.X, cur, krj);
		if(rt == -1) continue;
		return miin(rt, tmp.Y);
	}
	return -1;
}

void izbrisi(int i){
	int a = edg[i].Y.X, b = edg[i].Y.Y;
	v[a].erase(find(v[a].begin(), v[a].end(), (pii){b, i}));
	v[b].erase(find(v[b].begin(), v[b].end(), (pii){a, i}));
}

int main(){
	scanf("%d%d", &n, &m);
	for(int i = 0;i < m;i++){
		int a, b, w; scanf("%d%d%d", &a, &b, &w);
		edg.PB({w, {a, b}});
	}
	edg.PB({INF, {-1, -1}});
	sort(edg.begin(), edg.end());
	for(int i = 0;i < m;i++){
		int a = edg[i].Y.X, b = edg[i].Y.Y, w = edg[i].X;
		int rt = get_path(a, a, b);
		if(rt == -1)
			bar[i] = -INF; 
		else{
			bar[i] = edg[rt].X + (w - edg[rt].X + 2) / 2;
			izbrisi(rt);
		}
		v[a].PB({b, i}); v[b].PB({a, i});
	}
	for(int i = 1;i <= n;i++) v[i].clear();
	kofa = 1; edg.back().X = -INF;
	for(int i = m - 1;i >= 0;i--){
		int a = edg[i].Y.X, b = edg[i].Y.Y, w = edg[i].X;
		int rt = get_path(a, a, b);
		if(rt == -1)
			gor[i] = INF; 
		else{
			gor[i] = w + (edg[rt].X - w) / 2;
			izbrisi(rt);
		}
		v[a].PB({b, i}); v[b].PB({a, i});
	}
	scanf("%d", &q);
	for(int i = 0;i < q;i++) scanf("%d", qq + i); 
	qq[q] = (ll)INF + 1;
	for(int j = 0;j < m;j++){
		int l = lower_bound(qq, qq + q, bar[j]) - qq;
		int dl = upper_bound(qq, qq + q, edg[j].X) - qq;
		int r = upper_bound(qq, qq + q, gor[j]) - qq;
		odg1[l] += edg[j].X; odg1[dl] -= edg[j].X;
		cnt1[l]++; cnt1[dl]--;
		odg2[dl] += edg[j].X; odg2[r] -= edg[j].X;
		cnt2[dl]++; cnt2[r]--;
	}
	for(int j = 0;j < q;j++){
		if(j){ 
			odg1[j] += odg1[j - 1]; odg2[j] += odg2[j - 1];
			cnt1[j] += cnt1[j - 1]; cnt2[j] += cnt2[j - 1];
		}
		printf("%lld\n", odg1[j] - cnt1[j] * qq[j] + qq[j] * cnt2[j] - odg2[j]);
	}
	return 0;
}

Compilation message (stderr)

reconstruction.cpp: In function 'int main()':
reconstruction.cpp:49:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
reconstruction.cpp:51:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |   int a, b, w; scanf("%d%d%d", &a, &b, &w);
      |                ~~~~~^~~~~~~~~~~~~~~~~~~~~~
reconstruction.cpp:80:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |  scanf("%d", &q);
      |  ~~~~~^~~~~~~~~~
reconstruction.cpp:81:32: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |  for(int i = 0;i < q;i++) scanf("%d", qq + i);
      |                           ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 3 / 3
• Subtask 2: 4 / 4
• Subtask 3: 7 / 7
• Subtask 4: 28 / 28
• Subtask 5: 35 / 35
• Subtask 6: 23 / 23