oj.uz

Submission #336644

# Submission time Handle Problem Language Result Execution time Memory
336644 2020-12-16T07:44:38 Z keta_tsimakuridze Islands (IOI08_islands) C++14
90 / 100
 1161 ms 131076 KB 
#include<bits/stdc++.h>
#define f first
#define s second
using namespace std;
const int N=1e6+5;
long long mx,ans1,mx1,sz,ans,dm[N];
int n,m,a[N],b[N],fix[N],c,k,u,v;
vector<pair<int,long long> >V[N],cycle;
void dfs(int u,int p,long long h,int S){
	if(!fix[u])fix[u]=1;
	if(h>mx) {
		mx=h; c=u;
	}
	for(int i=0;i<V[u].size();i++){
		if((fix[V[u][i].f]!=2 || V[u][i].f==S) && V[u][i].f!=p){
			dfs(V[u][i].f,u,h+V[u][i].s,S);
		}
	}
}
void diameter(int u){
    mx=-1;
	dfs(u,0,0,u);dm[u]=mx;
	dfs(c,0,0,u);
	ans1=max(ans1,mx);	
}
int main(){
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n;
	for(k=1;k<=n;k++){
		cin>>a[k]>>b[k];
		V[a[k]].push_back({k,b[k]});
		V[k].push_back({a[k],b[k]});
	}
	for(k=1;k<=n;k++){
		if(!fix[k]){   
			u=k;
			ans1=0; sz=0; cycle.clear();
			while(!fix[u]){
				fix[u]=1;
				u=a[u];
			} 
			while(fix[u]!=2){
				fix[u]=2;
				u=a[u];
				cycle.push_back({u,b[u]});
				sz+=b[u];
			}
			for(int i=0;i<cycle.size();i++){
				diameter(cycle[i].f);
			} 
			mx=mx1=dm[cycle[0].f]; ans1=max(ans1,sz-cycle[0].s);
			long long bef=cycle[0].s;
			for(int i=1;i<cycle.size();i++){
			
				ans1=max(ans1,bef+mx+dm[cycle[i].f]);
				ans1=max(ans1,sz+mx1-bef+dm[cycle[i].f]);
				mx=max(mx,dm[cycle[i].f]-bef);
				mx1=max(mx1,dm[cycle[i].f]+bef);
				bef+=cycle[i].s;
			}
			ans+=ans1;
		} 
	}
	cout<<ans;
}

Compilation message

islands.cpp: In function 'void dfs(int, int, long long int, int)':
islands.cpp:14:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |  for(int i=0;i<V[u].size();i++){
      |              ~^~~~~~~~~~~~
islands.cpp: In function 'int main()':
islands.cpp:48:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |    for(int i=0;i<cycle.size();i++){
      |                ~^~~~~~~~~~~~~
islands.cpp:53:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |    for(int i=1;i<cycle.size();i++){
      |                ~^~~~~~~~~~~~~

Subtask #1
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23788 KB Output is correct
2 Correct 17 ms 23916 KB Output is correct
3 Correct 17 ms 23916 KB Output is correct
4 Correct 16 ms 23788 KB Output is correct
5 Correct 17 ms 23788 KB Output is correct
6 Correct 16 ms 23788 KB Output is correct
7 Correct 17 ms 23916 KB Output is correct
8 Correct 17 ms 23916 KB Output is correct
9 Correct 19 ms 23916 KB Output is correct
10 Correct 16 ms 23916 KB Output is correct
11 Correct 17 ms 23916 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 24044 KB Output is correct
2 Correct 17 ms 24044 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 24044 KB Output is correct
2 Correct 22 ms 24300 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 25196 KB Output is correct
2 Correct 34 ms 26984 KB Output is correct
3 Correct 28 ms 25580 KB Output is correct
4 Correct 22 ms 24684 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 27992 KB Output is correct
2 Correct 53 ms 31460 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 38500 KB Output is correct
2 Correct 104 ms 40156 KB Output is correct
3 Correct 121 ms 44764 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 52460 KB Output is correct
2 Correct 191 ms 63192 KB Output is correct
3 Correct 225 ms 67672 KB Output is correct
4 Correct 262 ms 76376 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 348 ms 82792 KB Output is correct
2 Correct 773 ms 104328 KB Output is correct
3 Correct 303 ms 81260 KB Output is correct
4 Correct 377 ms 100428 KB Output is correct
5 Correct 373 ms 100808 KB Output is correct
6 Correct 1161 ms 88556 KB Output is correct
7 Correct 410 ms 108472 KB Output is correct

Subtask #9
0 / 10.0

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