Submission #400295

#	Time	Username	Problem	Language	Result	Execution time	Memory
400295		ly20	Islands (IOI08_islands)	C++17	90 / 100	1351 ms	131076 KiB

islands

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 10;
const long long INF = 1123456789012345678;
vector <int> inv[MAXN], invp[MAXN];
int grafo[MAXN], p[MAXN];
int grau[MAXN];
long long tot;
long long resp;
long long rs;
long long mx, id;
int lm;
void dfs3(int v, int pai, long long d) {
	//printf("%d %lld\n", v, d);
	if(d > mx) {
		mx = d; id = v;
	}
	for(int i = 0; i < inv[v].size(); i++) {
		int viz = inv[v][i], ps = invp[v][i];
		if(viz == pai || (grau[viz] != 0 && viz != lm)) continue;
		dfs3(viz, v, d + ps);
	}
	if(grafo[v] != pai && (grau[grafo[v]] == 0 || grafo[v] == lm)) {
		dfs3(grafo[v], v, d + p[v]);
	}
}
void dfs(int v) {
	grau[v]++;
	tot += p[v];
	if(grau[grafo[v]] == 1) dfs(grafo[v]);
}
long long m1, m2, at;
void dfs2(int v) {
	lm = v;
	grau[v]++;
	mx = 0; id = v;
	dfs3(id, id, 0);
	rs = max(rs, max(m1 + at + mx, m2 - at + mx + tot));
	m1 = max(m1, mx - at);
	m2 = max(m2, mx + at);
	at += p[v];
	//printf("oi\n");
	dfs3(id, id, 0);
	//printf("%d %lld\n", v, mx);
	rs = max(rs, mx);
	if(grau[grafo[v]] == 2) dfs2(grafo[v]);
}
int main() {
	int n;
	scanf("%d", &n);
	//printf("%d\n", n);
	for(int i = 1; i <= n; i++) {
		scanf("%d %d", &grafo[i], &p[i]);
		inv[grafo[i]].push_back(i); invp[grafo[i]].push_back(p[i]);
		grau[grafo[i]]++;
	}
	//printf("oi\n");
	queue <int> fila;
	for(int i = 1; i <= n; i++) {
		if(grau[i] == 0) {
			fila.push(i);
		}
	}
	//printf("oi\n");
	while(!fila.empty()) {
		int cur = fila.front(); fila.pop();
		grau[grafo[cur]]--;
		if(grau[grafo[cur]] == 0) fila.push(grafo[cur]);
	}
	//printf("oi\n");
	for(int i = 1; i <= n; i++) {
		if(grau[i] == 1) {
			tot = 0;
			rs = 0;
			at = 0;
			m1 = -INF; m2 = -INF;
			dfs(i);
			//printf("oi\n");
			dfs2(i);
			resp += rs;
			//printf("oi\n");
		}
	}
	//printf("oi\n");
	printf("%lld\n", resp);
}

Compilation message (stderr)

islands.cpp: In function 'void dfs3(int, int, long long int)':
islands.cpp:18:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |  for(int i = 0; i < inv[v].size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~
islands.cpp: In function 'int main()':
islands.cpp:50:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   50 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
islands.cpp:53:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   53 |   scanf("%d %d", &grafo[i], &p[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• 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: 10 / 10
• Subtask 9: 0 / 10