oj.uz

Submission #1102215

# Submission time Handle Problem Language Result Execution time Memory
1102215 2024-10-17T16:21:54 Z _rain_ Islands (IOI08_islands) C++14
27 / 100
 837 ms 131072 KB 
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int,int> ii;
#define fi first 
#define se second

const int N = 1000000;
vector<ii> adj[N+2];
int en[N+2],l[N+2],id[N+2],times=0,n,root;
vector<int> s;
bool vis[N+2];
ll mxw,d[N+2];
void add_edge(int u , int v , int l){
	adj[u].push_back({v,l});
	adj[v].push_back({u,l});
	return;
}
void search(int u){
	s.push_back(u);
	id[u]=times;
	for (auto& x : adj[u]){
		int to=x.first , w=x.second;
		if (id[to]!=0) continue;
		search(to);
	}
	return;
}
void dfs(int u , int p){
	vis[u] = true;
	if (mxw <= d[u]){
		root=u;
		mxw=d[u];
	}
	for (auto& x : adj[u]){
		int to=x.first , w=x.second;
		if (vis[to]) continue;
		d[to]=d[u]+w;
		dfs(to,u);
	}
	return;
}
void Find(int root){
	mxw = 0;
	for (auto& u:s) {
		d[u]=vis[u]=0;
	}
	dfs(root,root);
}



int32_t main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; ++i){
		cin >> en[i] >> l[i];
		add_edge(i,en[i],l[i]);
	}
	for (int i = 1; i <= n; ++i) {
		sort(adj[i].begin(),adj[i].end(),
		[=](ii x , ii y){
				if (x.se!=y.se) return x.se>y.se;
		});
	}
	ll ans=0;
	for (int i = 1; i <= n; ++i){
		if (!id[i]){
			++times,s.clear();
			search(i);
			root = i;
			Find(root);
			Find(root);
			ans+=mxw;
		}
	}
	cout << ans;
}

Compilation message

islands.cpp: In function 'void search(int)':
islands.cpp:24:20: warning: unused variable 'w' [-Wunused-variable]
   24 |   int to=x.first , w=x.second;
      |                    ^
islands.cpp: In lambda function:
islands.cpp:66:3: warning: control reaches end of non-void function [-Wreturn-type]
   66 |   });
      |   ^

Subtask #1
27.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 33876 KB Output is correct
2 Correct 6 ms 33980 KB Output is correct
3 Incorrect 8 ms 33876 KB Output isn't correct
4 Correct 6 ms 34048 KB Output is correct
5 Correct 8 ms 34052 KB Output is correct
6 Correct 7 ms 33876 KB Output is correct
7 Correct 6 ms 33876 KB Output is correct
8 Incorrect 7 ms 33876 KB Output isn't correct
9 Correct 6 ms 34036 KB Output is correct
10 Correct 6 ms 33876 KB Output is correct
11 Correct 6 ms 34016 KB Output is correct

Subtask #2
0 / 3.0

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

Subtask #3
0 / 4.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 40316 KB Output is correct
2 Incorrect 37 ms 42212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 48064 KB Output is correct
2 Correct 78 ms 50940 KB Output is correct
3 Incorrect 100 ms 59700 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 511 ms 107580 KB Output is correct
2 Incorrect 837 ms 131072 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

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