oj.uz

Submission #587966

# Submission time Handle Problem Language Result Execution time Memory
587966 2022-07-02T15:16:08 Z MrDeboo Dreaming (IOI13_dreaming) C++17
14 / 100
 195 ms 19852 KB 
#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
vector<pair<int,int>>vct[100000];
vector<pair<int,int>>vec[100000];
int fath[100000];
int val[100000];
int n,m,l,f,ans;
int diam(int in){
	deque<pair<int,int>>dq={{in,0}};
	map<int,bool>vis;
	vis[in]=1;
	int x=0,y=0;
	while(dq.size()){
		int a=dq.front().first,b=dq.front().second;
		dq.pop_front();
		if(b>=y){
			x=a;
			y=b;
		}
		for(auto &i:vct[a]){
			if(!vis[i.first]){
				vis[i.first]=1;
				dq.push_back({i.first,b+i.second});
			}
		}
	}
	dq.push_back({x,0});
	x=0;y=0;
	vis.clear();
    vis[dq.back().first]=1;
	while(dq.size()){
		int a=dq.front().first,b=dq.front().second;
		dq.pop_front();
		if(b>=y){
			x=a;
			y=b;
		}
		for(auto &i:vct[a]){
            if(!vis[i.first]){
				vis[i.first]=1;
				dq.push_back({i.first,b+i.second});
			}
		}
	}
	return y;
}
int dfs1(int in){
	for(auto &i:vec[in])val[in]=max(val[in],dfs1(i.first)+i.second);
	return val[in];
}
void dfs2(int in,int x){
	f=min(f,max(x,val[in]));
	for(auto &i:vec[in])dfs2(i.first,x+i.second);
}
int travelTime(int N, int M, int L, int a[], int b[], int t[]){
	n=N,m=M,l=L;
    for(int i=0;i<m;i++){
        vct[a[i]].push_back({b[i],t[i]});
        vct[b[i]].push_back({a[i],t[i]});
    }
    vector<int>vis(n);
    deque<int>v;
    for(int i=0;i<n;i++){
        if(vis[i])continue;
        vis[i]=1;
        vector<int>vc={i};
        {
            deque<int>dq={i};
            while(dq.size()){
                int a=dq.front();
                dq.pop_front();
                for(auto &w:vct[a]){
                    if(!vis[w.first]){
                        vis[w.first]=1;
						vec[a].push_back(w);
						fath[w.first]=a;
                        dq.push_back(w.first);
                        vc.push_back(w.first);
                    }
                }
            }
        }
        f=INT_MAX;
		ans=max(ans,diam(i));
		if(vc.size()==1)f=0;
		else{
			dfs1(i);
			f=min(f,val[i]);
			vector<pair<int,int>>V={{0,-1}};
			for(auto &w:vec[i])V.push_back({w.second+val[w.first],w.first});
			sort(V.begin(),V.end());
			for(auto &w:vec[i]){
				if(w.first==V.back().second)dfs2(w.first,V[V.size()-2].first+w.second);
				else dfs2(w.first,V.back().first+w.second);
			}
		}
        v.push_back(f);
    }
    sort(v.begin(),v.end());
    if(v.size()>2)ans=max(ans,min(v[v.size()-2]+v[v.size()-3]+l*2,v[v.size()-2]+l+v.back()));
    else if(v.size()>1)ans=max(ans,v[v.size()-2]+l+v.back());
    return ans;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 19852 KB Output is correct
2 Correct 195 ms 19664 KB Output is correct
3 Correct 95 ms 15560 KB Output is correct
4 Correct 20 ms 7184 KB Output is correct
5 Correct 14 ms 6272 KB Output is correct
6 Correct 30 ms 8188 KB Output is correct
7 Correct 3 ms 5076 KB Output is correct
8 Correct 59 ms 10564 KB Output is correct
9 Correct 100 ms 12872 KB Output is correct
10 Correct 4 ms 5076 KB Output is correct
11 Correct 129 ms 14288 KB Output is correct
12 Correct 139 ms 16916 KB Output is correct
13 Correct 3 ms 5076 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 4 ms 4948 KB Output is correct
3 Incorrect 3 ms 4948 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 19852 KB Output is correct
2 Correct 195 ms 19664 KB Output is correct
3 Correct 95 ms 15560 KB Output is correct
4 Correct 20 ms 7184 KB Output is correct
5 Correct 14 ms 6272 KB Output is correct
6 Correct 30 ms 8188 KB Output is correct
7 Correct 3 ms 5076 KB Output is correct
8 Correct 59 ms 10564 KB Output is correct
9 Correct 100 ms 12872 KB Output is correct
10 Correct 4 ms 5076 KB Output is correct
11 Correct 129 ms 14288 KB Output is correct
12 Correct 139 ms 16916 KB Output is correct
13 Correct 3 ms 5076 KB Output is correct
14 Correct 3 ms 4948 KB Output is correct
15 Correct 4 ms 4948 KB Output is correct
16 Incorrect 3 ms 4948 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

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

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 4 ms 4948 KB Output is correct
3 Incorrect 3 ms 4948 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 19852 KB Output is correct
2 Correct 195 ms 19664 KB Output is correct
3 Correct 95 ms 15560 KB Output is correct
4 Correct 20 ms 7184 KB Output is correct
5 Correct 14 ms 6272 KB Output is correct
6 Correct 30 ms 8188 KB Output is correct
7 Correct 3 ms 5076 KB Output is correct
8 Correct 59 ms 10564 KB Output is correct
9 Correct 100 ms 12872 KB Output is correct
10 Correct 4 ms 5076 KB Output is correct
11 Correct 129 ms 14288 KB Output is correct
12 Correct 139 ms 16916 KB Output is correct
13 Correct 3 ms 5076 KB Output is correct
14 Correct 3 ms 4948 KB Output is correct
15 Correct 4 ms 4948 KB Output is correct
16 Incorrect 3 ms 4948 KB Output isn't correct
17 Halted 0 ms 0 KB -