Submission #224596

#	Time	Username	Problem	Language	Result	Execution time	Memory
224596		Kenzo_1114	Islands (IOI08_islands)	C++17	80 / 100	554 ms	131076 KiB

islands

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1000002;

int n, A, par[MAXN], ed, bg;
long long int dist[MAXN], mx_dist, ans, c[MAXN];
vector<int> graph[MAXN], cost[MAXN], tree, cycle;
bool mark[MAXN];

void dfs1(int v, int p)
{
//	printf("v = %d p = %d\n", v, p);
	tree.push_back(v);
	mark[v] = true;
	par[v] = p;
	bool aux = true;

	for(int i = 0; i < graph[v].size(); i++)
	{
		int cur = graph[v][i];
		
		if(cur == p && aux){	aux = false;	continue;	}
		if(mark[cur])
		{
			if(!bg && !ed)	ed = v, bg = cur, par[cur] = v, c[cur] = cost[v][i];
			continue;
		}

		c[cur] = cost[v][i];
		dfs1(cur, v);
	}

	return;
}

void dfs2(int v)
{
	mark[v] = true;
	tree.push_back(v);
	if(dist[v] > mx_dist) mx_dist = dist[v], A = v;

	for(int i = 0; i < graph[v].size(); i++)
	{
		int cur = graph[v][i];
		if(mark[cur])	continue;
		dist[cur] = dist[v] + cost[v][i];
		dfs2(cur);
	}

	return;
}

int main ()
{
	scanf("%d", &n);

	for(int i = 1, j, l; i <= n; i++)
	{
		scanf("%d %d", &j, &l);
		graph[i].push_back(j), cost[i].push_back(l);
		graph[j].push_back(i), cost[j].push_back(l);
	}

	for(int i = 1; i <= n; i++)
	{
		if(mark[i])	continue;

		bg = ed = 0;
		tree.clear(); cycle.clear();
		dfs1(i, i);

		int cur = ed;
		while(cur != bg)	cycle.push_back(cur), cur = par[cur];
		cycle.push_back(cur);

		for(int j = 0; j < tree.size(); j++)	mark[tree[j]] = false;
		for(int j = 0; j < cycle.size(); j++)	mark[cycle[j]] = true;

		long long int SCT = 0, SC = 0;
		long long int max_DI_SCI[5], ANS = 0;
		max_DI_SCI[0] = 0;
		max_DI_SCI[1] = 0;

		for(int j = 0; j < cycle.size(); j++)	SCT += c[cycle[j]];

		for(int j = 0; j < cycle.size(); j++)
		{
			int v = A = cycle[j];

			mark[v] = false, mx_dist = dist[v] = 0;
			tree.clear();
			dfs2(v);

			ANS = max(ANS, max_DI_SCI[0] + mx_dist + SC);
			ANS = max(ANS, max_DI_SCI[1] + mx_dist - SC);

			max_DI_SCI[0] = max(max_DI_SCI[0], mx_dist - SC);
			max_DI_SCI[1] = max(max_DI_SCI[1], mx_dist + SC + SCT);

			SC += c[v];

			for(int k = 0; k < tree.size(); k++)	mark[tree[k]] = false;
			dist[A] = 0; tree.clear();
			dfs2(A);

			ANS = max(ANS, mx_dist);
		}

		ans += ANS;
	}

	printf("%lld\n", ans);
}	

Compilation message (stderr)

islands.cpp: In function 'void dfs1(int, int)':
islands.cpp:18:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < graph[v].size(); i++)
                 ~~^~~~~~~~~~~~~~~~~
islands.cpp: In function 'void dfs2(int)':
islands.cpp:42:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < graph[v].size(); i++)
                 ~~^~~~~~~~~~~~~~~~~
islands.cpp: In function 'int main()':
islands.cpp:76:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j < tree.size(); j++) mark[tree[j]] = false;
                  ~~^~~~~~~~~~~~~
islands.cpp:77:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j < cycle.size(); j++) mark[cycle[j]] = true;
                  ~~^~~~~~~~~~~~~~
islands.cpp:84:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j < cycle.size(); j++) SCT += c[cycle[j]];
                  ~~^~~~~~~~~~~~~~
islands.cpp:86:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j < cycle.size(); j++)
                  ~~^~~~~~~~~~~~~~
islands.cpp:102:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int k = 0; k < tree.size(); k++) mark[tree[k]] = false;
                   ~~^~~~~~~~~~~~~
islands.cpp:55:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
islands.cpp:59:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &j, &l);
   ~~~~~^~~~~~~~~~~~~~~~~

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