oj.uz

답안 #588036

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
588036 2022-07-02T16:24:55 Z MrDeboo 꿈 (IOI13_dreaming) C++17
18 / 100
 243 ms 35908 KB 
#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
vector<pair<int,int>>vct[100000];
vector<pair<int,int>>vec[100000];
vector<pair<int,int>>voc[100000];
map<int,int>mp[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]){
        int g=dfs1(i.first)+i.second;
        val[in]=max(val[in],g);
        voc[in].push_back({g,i.first});
    }
    sort(voc[in].begin(),voc[in].end());
    return val[in];
}
void dfs2(int in,int x){
    int k=voc[fath[in]].size()-1;
    if(voc[fath[in]][k].second==in)k--;
    x=max(x,voc[fath[in]][k].first+mp[fath[in]][in]);
	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[]){
    for(int i=0;i<100000;i++)voc[i].push_back({0,-1});
	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;
                        mp[a][w.first]=w.second;
                        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+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());
    while(v.size()>1){
        ans=max(ans,v.back()+l+v[0]);
        v.back()=max(v.back(),v[0]+l);
        v.pop_front();
    }
    return ans;
}

Subtask #1
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 220 ms 35908 KB Output is correct
2 Correct 243 ms 35556 KB Output is correct
3 Correct 158 ms 30184 KB Output is correct
4 Correct 36 ms 18128 KB Output is correct
5 Correct 25 ms 16980 KB Output is correct
6 Correct 44 ms 19632 KB Output is correct
7 Incorrect 12 ms 15188 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 15144 KB Output is correct
2 Correct 10 ms 15164 KB Output is correct
3 Correct 11 ms 15108 KB Output is correct
4 Incorrect 14 ms 15188 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 220 ms 35908 KB Output is correct
2 Correct 243 ms 35556 KB Output is correct
3 Correct 158 ms 30184 KB Output is correct
4 Correct 36 ms 18128 KB Output is correct
5 Correct 25 ms 16980 KB Output is correct
6 Correct 44 ms 19632 KB Output is correct
7 Incorrect 12 ms 15188 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 65 ms 21288 KB Output is correct
2 Correct 60 ms 21336 KB Output is correct
3 Correct 59 ms 21248 KB Output is correct
4 Correct 59 ms 21320 KB Output is correct
5 Correct 61 ms 21200 KB Output is correct
6 Correct 64 ms 21664 KB Output is correct
7 Correct 62 ms 21480 KB Output is correct
8 Correct 67 ms 21156 KB Output is correct
9 Correct 85 ms 21128 KB Output is correct
10 Correct 69 ms 21464 KB Output is correct
11 Correct 11 ms 15204 KB Output is correct
12 Correct 36 ms 16592 KB Output is correct
13 Correct 35 ms 16684 KB Output is correct
14 Correct 35 ms 16652 KB Output is correct
15 Correct 34 ms 16628 KB Output is correct
16 Correct 34 ms 16596 KB Output is correct
17 Correct 38 ms 16212 KB Output is correct
18 Correct 38 ms 16732 KB Output is correct
19 Correct 36 ms 16588 KB Output is correct
20 Correct 12 ms 15188 KB Output is correct
21 Correct 11 ms 15184 KB Output is correct
22 Correct 12 ms 15316 KB Output is correct
23 Correct 33 ms 16596 KB Output is correct

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 15144 KB Output is correct
2 Correct 10 ms 15164 KB Output is correct
3 Correct 11 ms 15108 KB Output is correct
4 Incorrect 14 ms 15188 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 220 ms 35908 KB Output is correct
2 Correct 243 ms 35556 KB Output is correct
3 Correct 158 ms 30184 KB Output is correct
4 Correct 36 ms 18128 KB Output is correct
5 Correct 25 ms 16980 KB Output is correct
6 Correct 44 ms 19632 KB Output is correct
7 Incorrect 12 ms 15188 KB Output isn't correct
8 Halted 0 ms 0 KB -