oj.uz

Submission #400295

# Submission time Handle Problem Language Result Execution time Memory
400295 2021-05-07T19:44:45 Z ly20 Islands (IOI08_islands) C++17
90 / 100
 1351 ms 131076 KB 
#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

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.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 47272 KB Output is correct
2 Correct 25 ms 47188 KB Output is correct
3 Correct 26 ms 47276 KB Output is correct
4 Correct 25 ms 47240 KB Output is correct
5 Correct 28 ms 47208 KB Output is correct
6 Correct 26 ms 47236 KB Output is correct
7 Correct 26 ms 47192 KB Output is correct
8 Correct 26 ms 47180 KB Output is correct
9 Correct 25 ms 47220 KB Output is correct
10 Correct 26 ms 47276 KB Output is correct
11 Correct 29 ms 47184 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 47212 KB Output is correct
2 Correct 26 ms 47308 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 47320 KB Output is correct
2 Correct 27 ms 47436 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 48156 KB Output is correct
2 Correct 44 ms 49160 KB Output is correct
3 Correct 37 ms 48588 KB Output is correct
4 Correct 31 ms 47940 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 50096 KB Output is correct
2 Correct 71 ms 53956 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 59356 KB Output is correct
2 Correct 124 ms 65984 KB Output is correct
3 Correct 142 ms 63584 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 74976 KB Output is correct
2 Correct 234 ms 75488 KB Output is correct
3 Correct 267 ms 96552 KB Output is correct
4 Correct 292 ms 89580 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 336 ms 82728 KB Output is correct
2 Correct 813 ms 106616 KB Output is correct
3 Correct 365 ms 98316 KB Output is correct
4 Correct 466 ms 109232 KB Output is correct
5 Correct 422 ms 104516 KB Output is correct
6 Correct 1351 ms 112968 KB Output is correct
7 Correct 459 ms 112612 KB Output is correct

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 432 ms 131076 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -