Submission #923284

#	Time	Username	Problem	Language	Result	Execution time	Memory
923284		findingFish	Roller Coaster Railroad (IOI16_railroad)	C++17	100 / 100	113 ms	24540 KiB

railroad

#include <bits/stdc++.h>
#include "railroad.h"
using namespace std;

struct data1 {
  int x, y, z;
  data1 () {} 
  data1 (int _x, int _y, int _z) {//y for section No, z to diff whether x is s or t.
    x = _x, y = _y, z = _z;
  }
  bool operator < (const data1 &d) const {
    return x < d.x;
  }
};

const int INF = 2e9 + 10;

vector <int> p;

int find (int x) {
  return p[x] == x ? x : p[x] = find(p[x]);
}

bool merge (int x, int y) {
  x = find(x), y = find(y);
  return p[x] = y, x != y;
}

long long plan_roller_coaster (vector <int> s, vector <int> t) {
	s.push_back(INF);
	t.push_back(1);
	int n = (int) s.size();

	for (int i = 0; i < n; ++i) {
		p.push_back(i);
	}

	vector <data1> good;//size of good is 2n vetex, including s and t.
	for (int i = 0; i < n; ++i) {
		good.emplace_back(s[i], i, 1);
		good.emplace_back(t[i], i, -1);
	}
	sort(good.begin(), good.end());//non-descending of both s and t

	vector <data1> edge;//2n-1 in total
	for (int i = 0; i + 1 < n + n; ++i) {
		edge.emplace_back(good[i + 1].x - good[i].x, good[i].y, good[i + 1].y);
	}
	sort(edge.begin(), edge.end());



	long long ans = 0;

	for (int i = 0, diff = 0; i + 1 < n + n; ++i) {
		diff += good[i].z;
		ans += max(0, diff) * 1LL * (good[i + 1].x - good[i].x);//diff = -1 then 0
		
		if ((diff != 0) or (good[i].x == good[i + 1].x)) {
			merge(good[i].y, good[i + 1].y);
		}
	}

	for (int i = 0; i + 1 < n + n; ++i) {
		if (merge(edge[i].y, edge[i].z)) {
			ans += 1LL * edge[i].x;
		}
	}

	return ans;
}

• Subtask 1: 11 / 11
• Subtask 2: 23 / 23
• Subtask 3: 30 / 30
• Subtask 4: 36 / 36