oj.uz

답안 #587900

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
587900 2022-07-02T13:42:39 Z MrDeboo 꿈 (IOI13_dreaming) C++17
32 / 100
 182 ms 19860 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());
    while(v.size()>1){
        ans=max(ans,v[0]+l+v.back());
        v.back()=max(v.back(),v[0]+l);
        v.pop_front();
    }
    return ans;
}

Subtask #1
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 177 ms 19860 KB Output is correct
2 Correct 179 ms 19552 KB Output is correct
3 Correct 98 ms 15528 KB Output is correct
4 Correct 19 ms 7180 KB Output is correct
5 Correct 14 ms 6276 KB Output is correct
6 Correct 29 ms 8176 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 70 ms 10544 KB Output is correct
9 Correct 104 ms 12760 KB Output is correct
10 Correct 3 ms 5076 KB Output is correct
11 Correct 132 ms 14288 KB Output is correct
12 Correct 182 ms 17072 KB Output is correct
13 Correct 3 ms 5076 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 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

# 결과 실행 시간 메모리 Grader output
1 Correct 177 ms 19860 KB Output is correct
2 Correct 179 ms 19552 KB Output is correct
3 Correct 98 ms 15528 KB Output is correct
4 Correct 19 ms 7180 KB Output is correct
5 Correct 14 ms 6276 KB Output is correct
6 Correct 29 ms 8176 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 70 ms 10544 KB Output is correct
9 Correct 104 ms 12760 KB Output is correct
10 Correct 3 ms 5076 KB Output is correct
11 Correct 132 ms 14288 KB Output is correct
12 Correct 182 ms 17072 KB Output is correct
13 Correct 3 ms 5076 KB Output is correct
14 Correct 3 ms 4948 KB Output is correct
15 Correct 3 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

# 결과 실행 시간 메모리 Grader output
1 Correct 43 ms 9628 KB Output is correct
2 Correct 44 ms 9596 KB Output is correct
3 Correct 58 ms 9548 KB Output is correct
4 Correct 42 ms 9580 KB Output is correct
5 Correct 66 ms 9552 KB Output is correct
6 Correct 65 ms 9924 KB Output is correct
7 Correct 49 ms 9768 KB Output is correct
8 Correct 43 ms 9548 KB Output is correct
9 Correct 41 ms 9480 KB Output is correct
10 Correct 44 ms 9724 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 26 ms 6484 KB Output is correct
13 Correct 26 ms 6484 KB Output is correct
14 Correct 26 ms 6392 KB Output is correct
15 Correct 25 ms 6536 KB Output is correct
16 Correct 26 ms 6352 KB Output is correct
17 Correct 26 ms 6032 KB Output is correct
18 Correct 36 ms 6536 KB Output is correct
19 Correct 24 ms 6384 KB Output is correct
20 Correct 3 ms 4948 KB Output is correct
21 Correct 3 ms 4948 KB Output is correct
22 Correct 3 ms 4948 KB Output is correct
23 Correct 28 ms 6376 KB Output is correct

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 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

# 결과 실행 시간 메모리 Grader output
1 Correct 177 ms 19860 KB Output is correct
2 Correct 179 ms 19552 KB Output is correct
3 Correct 98 ms 15528 KB Output is correct
4 Correct 19 ms 7180 KB Output is correct
5 Correct 14 ms 6276 KB Output is correct
6 Correct 29 ms 8176 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 70 ms 10544 KB Output is correct
9 Correct 104 ms 12760 KB Output is correct
10 Correct 3 ms 5076 KB Output is correct
11 Correct 132 ms 14288 KB Output is correct
12 Correct 182 ms 17072 KB Output is correct
13 Correct 3 ms 5076 KB Output is correct
14 Correct 3 ms 4948 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Incorrect 2 ms 4948 KB Output isn't correct
17 Halted 0 ms 0 KB -