oj.uz

답안 #156956

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
156956 2019-10-08T14:19:45 Z farmersrice Islands (IOI08_islands) C++17
0 / 100
 376 ms 131072 KB 
#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

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.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 219 ms 131072 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Incorrect 91 ms 94328 KB Output isn't correct
3 Incorrect 90 ms 94328 KB Output isn't correct
4 Incorrect 90 ms 94456 KB Output isn't correct
5 Incorrect 91 ms 94316 KB Output isn't correct
6 Incorrect 107 ms 94328 KB Output isn't correct
7 Runtime error 217 ms 131072 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Incorrect 90 ms 94328 KB Output isn't correct
9 Runtime error 227 ms 131072 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Incorrect 91 ms 94332 KB Output isn't correct
11 Runtime error 223 ms 131072 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #2
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 91 ms 94456 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 93 ms 94584 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 102 ms 95716 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 143 ms 101604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 234 ms 115676 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 309 ms 128692 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 292 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 376 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -