oj.uz

답안 #226489

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
226489 2020-04-24T00:51:37 Z Kenzo_1114 Islands (IOI08_islands) C++11
80 / 100
 551 ms 131076 KB 
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1000002;

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

void dfs1()
{
//	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;
		}

		int auxV = V, auxP = P;
		c[cur] = cost[V][i];
		P = V, V = cur;
		dfs1();
		V = auxV, P = auxP;
	}
}

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

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

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();
		V = P = i;
		dfs1();

		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[2] = {0, 0}, max_DJ_SCJ[2] = {0, 0}, ANS = 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 = 0;
			tree.clear();
			V = v;
			dfs2();

			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;
			tree.clear();
			V = A;
			dfs2();

			ANS = max(ANS, mx_dist);
		}

		ans += ANS;
	}

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

Compilation message

islands.cpp: In function 'void dfs1()':
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()':
islands.cpp:43: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:80: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:81: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:86: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:88:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j < cycle.size(); j++)
                  ~~^~~~~~~~~~~~~~
islands.cpp:105: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:84:41: warning: unused variable 'max_DJ_SCJ' [-Wunused-variable]
   long long int max_DI_SCI[2] = {0, 0}, max_DJ_SCJ[2] = {0, 0}, ANS = 0;
                                         ^~~~~~~~~~
islands.cpp:58:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
islands.cpp:62: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.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 47360 KB Output is correct
2 Correct 29 ms 47360 KB Output is correct
3 Correct 39 ms 47352 KB Output is correct
4 Correct 29 ms 47360 KB Output is correct
5 Correct 28 ms 47360 KB Output is correct
6 Correct 29 ms 47232 KB Output is correct
7 Correct 28 ms 47360 KB Output is correct
8 Correct 29 ms 47360 KB Output is correct
9 Correct 29 ms 47360 KB Output is correct
10 Correct 29 ms 47360 KB Output is correct
11 Correct 28 ms 47360 KB Output is correct

Subtask #2
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 47488 KB Output is correct
2 Correct 30 ms 47360 KB Output is correct

Subtask #3
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 47488 KB Output is correct
2 Correct 34 ms 47744 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 48640 KB Output is correct
2 Correct 55 ms 51320 KB Output is correct
3 Correct 46 ms 49152 KB Output is correct
4 Correct 37 ms 48256 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 65 ms 52728 KB Output is correct
2 Correct 96 ms 56312 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 160 ms 65240 KB Output is correct
2 Correct 160 ms 70260 KB Output is correct
3 Correct 201 ms 78068 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 268 ms 78972 KB Output is correct
2 Correct 318 ms 101324 KB Output is correct
3 Correct 369 ms 112100 KB Output is correct
4 Correct 425 ms 125668 KB Output is correct

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 475 ms 131076 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 551 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -