Submission #216724

#	Time	Username	Problem	Language	Result	Execution time	Memory
216724		peuch	Islands (IOI08_islands)	C++17	18 / 100	619 ms	131076 KiB

islands

#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 = dfs4(aux);
		dist[i] = 0;
		aux = dfs3(i);
		dist[aux] = 0;
		aux2 = max(aux2, dfs2(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 (stderr)

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: 18 / 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