oj.uz

Submission #587894

# Submission time Handle Problem Language Result Execution time Memory
587894 2022-07-02T13:34:15 Z MrDeboo Dreaming (IOI13_dreaming) C++17
32 / 100
 174 ms 19848 KB 
#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
multiset<int>st;
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]});
    }
    deque<int>v;
    vector<int>vis(n);
    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);
			}
		}
        st.insert(f);
    }
    while(st.size()>1){
		int a=*st.begin();
		st.erase(st.begin());
		int b=*(--st.end());
        st.erase(--st.end());
		ans=max(ans,a+b+l);
        st.insert(max(a+l,b));
    }
    return ans;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 19848 KB Output is correct
2 Correct 161 ms 19556 KB Output is correct
3 Correct 110 ms 15520 KB Output is correct
4 Correct 22 ms 7192 KB Output is correct
5 Correct 16 ms 6228 KB Output is correct
6 Correct 31 ms 8164 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 65 ms 10620 KB Output is correct
9 Correct 84 ms 12784 KB Output is correct
10 Correct 3 ms 5028 KB Output is correct
11 Correct 118 ms 14296 KB Output is correct
12 Correct 156 ms 16964 KB Output is correct
13 Correct 3 ms 5140 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 2 ms 4948 KB Output is correct
3 Incorrect 2 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 174 ms 19848 KB Output is correct
2 Correct 161 ms 19556 KB Output is correct
3 Correct 110 ms 15520 KB Output is correct
4 Correct 22 ms 7192 KB Output is correct
5 Correct 16 ms 6228 KB Output is correct
6 Correct 31 ms 8164 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 65 ms 10620 KB Output is correct
9 Correct 84 ms 12784 KB Output is correct
10 Correct 3 ms 5028 KB Output is correct
11 Correct 118 ms 14296 KB Output is correct
12 Correct 156 ms 16964 KB Output is correct
13 Correct 3 ms 5140 KB Output is correct
14 Correct 3 ms 4948 KB Output is correct
15 Correct 2 ms 4948 KB Output is correct
16 Incorrect 2 ms 4948 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 12304 KB Output is correct
2 Correct 72 ms 12744 KB Output is correct
3 Correct 62 ms 12748 KB Output is correct
4 Correct 73 ms 12748 KB Output is correct
5 Correct 60 ms 12672 KB Output is correct
6 Correct 63 ms 13208 KB Output is correct
7 Correct 64 ms 12996 KB Output is correct
8 Correct 67 ms 12492 KB Output is correct
9 Correct 80 ms 12528 KB Output is correct
10 Correct 66 ms 12996 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 55 ms 10700 KB Output is correct
13 Correct 52 ms 10832 KB Output is correct
14 Correct 56 ms 10692 KB Output is correct
15 Correct 50 ms 10740 KB Output is correct
16 Correct 50 ms 10648 KB Output is correct
17 Correct 57 ms 10324 KB Output is correct
18 Correct 51 ms 10768 KB Output is correct
19 Correct 51 ms 10708 KB Output is correct
20 Correct 3 ms 4948 KB Output is correct
21 Correct 3 ms 4948 KB Output is correct
22 Correct 5 ms 5076 KB Output is correct
23 Correct 51 ms 10704 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Incorrect 2 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 174 ms 19848 KB Output is correct
2 Correct 161 ms 19556 KB Output is correct
3 Correct 110 ms 15520 KB Output is correct
4 Correct 22 ms 7192 KB Output is correct
5 Correct 16 ms 6228 KB Output is correct
6 Correct 31 ms 8164 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 65 ms 10620 KB Output is correct
9 Correct 84 ms 12784 KB Output is correct
10 Correct 3 ms 5028 KB Output is correct
11 Correct 118 ms 14296 KB Output is correct
12 Correct 156 ms 16964 KB Output is correct
13 Correct 3 ms 5140 KB Output is correct
14 Correct 3 ms 4948 KB Output is correct
15 Correct 2 ms 4948 KB Output is correct
16 Incorrect 2 ms 4948 KB Output isn't correct
17 Halted 0 ms 0 KB -