oj.uz

Submission #216722

# Submission time Handle Problem Language Result Execution time Memory
216722 2020-03-27T22:24:00 Z peuch Islands (IOI08_islands) C++17
15 / 100
 618 ms 131076 KB 
#include<bits/stdc++.h>
using namespace std;

const int MAXN = 1000000;

int n;
int marc[MAXN];
long long dist[MAXN];
 
vector<int> ar[MAXN];
vector<int> wg[MAXN];

int dfs1(int cur);
int dfs2(int cur);
int dfs3(int cur);
int dfs4(int cur);

int main(){
	scanf("%d", &n);
	for(int i = 1; i <= n; i++){
		int aux, auxd;
		scanf("%d %d", &aux, &auxd);
		ar[i].push_back(aux);
		ar[aux].push_back(i);
		wg[i].push_back(auxd);
		wg[aux].push_back(auxd);
	}
	long long ans = 0;
	for(int i = 1; i <= n; i++){
		if(marc[i] != 0) continue;
		dist[i] = 0;
		int aux = dfs1(i);
		dist[aux] = 0;
		int aux2 = dfs2(aux);
		dist[i] = 0;
		aux = dfs3(i);
		dist[aux] = 0;
		aux2 = max(aux2, dfs4(aux));
		ans += aux2;
	}
	printf("%lld\n", ans);
}

int dfs1(int cur){
	// printf("\t1-%d\n", cur);
	marc[cur] = 1;
	int ret = cur;
	int auxRet = dist[cur];
	for(int i = 0; i < ar[cur].size(); i++){
		int viz = ar[cur][i];
		int len = wg[cur][i];
		if(marc[viz] == 1) continue;
		dist[viz] = dist[cur] + len;
		int dfsVal = dfs1(viz);
		if(dist[dfsVal] > auxRet) ret = dfsVal, auxRet = dist[dfsVal];
 	} 
 	return ret;
}

int dfs2(int cur){
	// printf("\t2-%d\n", cur);
	marc[cur] = 2;
	int ret = dist[cur];
	for(int i = 0; i < ar[cur].size(); i++){
		int viz = ar[cur][i];
		int len = wg[cur][i];
		if(marc[viz] == 2) continue;
		dist[viz] = dist[cur] + len;
		ret = max(ret, dfs2(viz));
 	} 
 	return ret;
}

int dfs3(int cur){
	// printf("\t3-%d\n", cur);
	marc[cur] = 3;
	int ret = cur;
	int auxRet = dist[cur];
	for(int i = ar[cur].size() - 1; i >= 0; i--){
		int viz = ar[cur][i];
		int len = wg[cur][i];
		if(marc[viz] == 3) continue;
		dist[viz] = dist[cur] + len;
		int dfsVal = dfs3(viz);
		if(dist[dfsVal] > auxRet) ret = dfsVal, auxRet = dist[dfsVal];
 	} 
 	return ret;
}

int dfs4(int cur){
	// printf("\t4-%d\n", cur);
	marc[cur] = 4;
	int ret = dist[cur];
	for(int i = ar[cur].size() - 1; i >= 0; i--){
		int viz = ar[cur][i];
		int len = wg[cur][i];
		if(marc[viz] == 4) continue;
		dist[viz] = dist[cur] + len;
		ret = max(ret, dfs4(viz));
 	} 
 	return ret;
}

Compilation message

islands.cpp: In function 'int dfs1(int)':
islands.cpp:49:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < ar[cur].size(); i++){
                 ~~^~~~~~~~~~~~~~~~
islands.cpp: In function 'int dfs2(int)':
islands.cpp:64:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < ar[cur].size(); i++){
                 ~~^~~~~~~~~~~~~~~~
islands.cpp: In function 'int main()':
islands.cpp:19:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
islands.cpp:22:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &aux, &auxd);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 32 ms 47232 KB Output isn't correct
2 Correct 32 ms 47360 KB Output is correct
3 Incorrect 32 ms 47360 KB Output isn't correct
4 Correct 32 ms 47232 KB Output is correct
5 Correct 31 ms 47352 KB Output is correct
6 Incorrect 31 ms 47336 KB Output isn't correct
7 Incorrect 31 ms 47360 KB Output isn't correct
8 Incorrect 32 ms 47352 KB Output isn't correct
9 Incorrect 31 ms 47360 KB Output isn't correct
10 Correct 31 ms 47360 KB Output is correct
11 Correct 33 ms 47360 KB Output is correct

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 39 ms 47360 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 32 ms 47488 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 43 ms 48760 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 70 ms 53240 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 182 ms 66592 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 276 ms 83808 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 618 ms 131072 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 567 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -