Submission #156956

#	Time	Username	Problem	Language	Result	Execution time	Memory
156956		farmersrice	Islands (IOI08_islands)	C++17	0 / 100	376 ms	131072 KiB

islands

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pair2;
typedef pair<int, pair<int, int> > pair3;
typedef pair<int, pair<int, pair<int, int> > > pair4;
#define MAXN 2000013
#define INF 1000000000000000000LL
#define MOD 1000000007LL
#define IINF 1000000000
#define mp make_pair
#define pb push_back
#define remove pop
#define all(x) x.begin(), x.end()


int n, m;

vector<int> adj[MAXN];
vector<pair2> adjDist[MAXN];

int seen[MAXN];
int par[MAXN];
int dist[MAXN];
bool inCycle[MAXN];

ll depth[MAXN];

ll reldist[MAXN]; //relative distances to 0 node in cycle

vector<int> cycleNodes;
bool cycle;

ll cycleLength;

void getCycle(int cur, int par = -1) {
	if (cycle) return;

	cycleNodes.pb(cur);
	seen[cur] = true;
	for (pair2 p : adjDist[cur]) {
		if (p.first == par) continue;

		cycleLength += p.second;

		if (seen[p.first]) {
			cycle = true;
			return;
		}

		getCycle(p.first, cur);
		if (cycle) return;
		cycleLength -= p.second;
	}
	cycleNodes.pop_back();
}

void getDepth(int cur, int original, int par = -1, ll curDist = 0) {
	depth[original] = max(depth[original], curDist);

	for (pair2 p : adjDist[cur]) {
		int next = p.first;
		if (next == par) continue;
		if (inCycle[next]) continue;

		ll nextDist = p.second;

		getDepth(next, original, cur, curDist + nextDist);
	}
}

void getReldist(int cur, ll curDist = 0, int index = 0) {
	if (index >= cycleNodes.size()) return;

	reldist[index] = curDist;

	if (index == ((int)cycleNodes.size()) - 1) return;

	for (pair2 p : adjDist[cur]) {
		if (p.first != cycleNodes[index + 1]) continue;

		getReldist(p.first, curDist + p.second, index + 1);
	}
}

int main() {
	if (fopen("FILENAME.in", "r")) {
		freopen("FILENAME.in", "r", stdin);
		freopen("FILENAME.out", "w", stdout);
	}
	ios_base::sync_with_stdio(false); 
	cin.tie(NULL);

	cin >> n;

	for (int i = 0; i < n; i++) {
		int u, v, l;
		cin >> v >> l; u=i;v--;

		adj[u].pb(v);
		adj[v].pb(u);
		adjDist[u].pb(mp(v, l));
		adjDist[v].pb(mp(u, l));
	}

	//cout << "tha fucc " << endl;

	getCycle(0);

	for (int i : cycleNodes) {
		inCycle[i] = true;
	}

	for (int i : cycleNodes) {
		getDepth(i, i);
	}

	vector<int> paddedCycle = cycleNodes;

	for (int i : cycleNodes) {
		paddedCycle.pb(i);
	}

	getReldist(cycleNodes[0]);

	multiset<ll> dists;

	for (int i = 0; i < cycleNodes.size(); i++) {
		dists.insert(depth[cycleNodes[i]] - reldist[i]);
	}

	//cout << "cycle length is " << cycleLength << endl;

	ll answer = INF;
	for (int i = (int) cycleNodes.size(); i < paddedCycle.size(); i++) {
		int corr = i - (int)cycleNodes.size();

		//Remove corr from the multiset
		dists.erase(dists.find(depth[cycleNodes[corr]] - reldist[corr]));

		ll best = *(--dists.end());

		answer = min(answer, best + depth[cycleNodes[corr]] + cycleLength + reldist[corr]);

		dists.insert(depth[cycleNodes[corr]] - reldist[corr] - cycleLength);
	}
	cout << answer << endl;
}

//GCD GCD GCD USE GCD IN MATH

Compilation message (stderr)

islands.cpp: In function 'void getReldist(int, ll, int)':
islands.cpp:74:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (index >= cycleNodes.size()) return;
      ~~~~~~^~~~~~~~~~~~~~~~~~~~
islands.cpp: In function 'int main()':
islands.cpp:129:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < cycleNodes.size(); i++) {
                  ~~^~~~~~~~~~~~~~~~~~~
islands.cpp:136:42: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = (int) cycleNodes.size(); i < paddedCycle.size(); i++) {
                                        ~~^~~~~~~~~~~~~~~~~~~~
islands.cpp:89:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen("FILENAME.in", "r", stdin);
   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
islands.cpp:90:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen("FILENAME.out", "w", stdout);
   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 33
• Subtask 2: 0 / 3
• Subtask 3: 0 / 4
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10