oj.uz

Submission #297855

# Submission time Handle Problem Language Result Execution time Memory
297855 2020-09-12T05:20:53 Z Bill_00 Dreaming (IOI13_dreaming) C++14
32 / 100
 88 ms 15352 KB 
#include "dreaming.h"
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
using namespace std;
vector<long long>vec;
long long vis[100001],id,p=0,path,res=0;
long long cost[100001];
int go[100001];
vector<pair<int,long long> >adj[100001];
void dfsd(int u,int v,long long w){
	cost[u]=w;
	if(w>path){
		id=u;
		path=w;
	}
	go[u]=v;
	for(int i=0;i<adj[u].size();i++){
		int f=adj[u][i].ff;
		long long s=adj[u][i].ss;
		if(f!=v){
			dfsd(f,u,w+s);
		}
	}
	
}
void dfs(int u,int v,int w){
	vis[u]=1;
	if(w>p){
		id=u;
		p=w;
	}
	for(int i=0;i<adj[u].size();i++){
		int f=adj[u][i].ff;
		long long s=adj[u][i].ss;
		if(f!=v){
			dfs(f,u,w+s);
		}
	}
}
int travelTime(int n, int m, int L, int a[], int b[], int t[]){
	for(int i=0;i<m;i++){
		adj[a[i]].pb(mp(b[i],(long long)t[i]));
		adj[b[i]].pb(mp(a[i],(long long)t[i]));
	}
    for(int i=0;i<n;i++){
    	if(!vis[i]){
    		path=0;
    		p=0;
    		id=0;
    		dfs(i,-1,0);
    		dfsd(id,-1,0);
    		res=max(res,path);
    		long long ans=1e18;
    		while(id!=-1){
    			ans=min(ans,max(path-cost[id],cost[id]));
    			id=go[id];
			}
			vec.pb(ans);
		}
	}
	sort(vec.begin(),vec.end());
	if(vec.size()>=2) res=max(res,vec[vec.size()-1]+vec[vec.size()-2]+L);
	if(vec.size()>2) res=max(res,vec[vec.size()-2]+vec[vec.size()-3]+2*L);
	return res;
}

Compilation message

dreaming.cpp: In function 'void dfsd(int, int, long long int)':
dreaming.cpp:20: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]
   20 |  for(int i=0;i<adj[u].size();i++){
      |              ~^~~~~~~~~~~~~~
dreaming.cpp: In function 'void dfs(int, int, int)':
dreaming.cpp:35: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]
   35 |  for(int i=0;i<adj[u].size();i++){
      |              ~^~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 15352 KB Output is correct
2 Correct 69 ms 15352 KB Output is correct
3 Correct 48 ms 11128 KB Output is correct
4 Correct 10 ms 4608 KB Output is correct
5 Correct 9 ms 3944 KB Output is correct
6 Correct 17 ms 5632 KB Output is correct
7 Correct 2 ms 2688 KB Output is correct
8 Correct 33 ms 7676 KB Output is correct
9 Correct 43 ms 9464 KB Output is correct
10 Correct 2 ms 2816 KB Output is correct
11 Correct 69 ms 11896 KB Output is correct
12 Correct 88 ms 13688 KB Output is correct
13 Correct 3 ms 2816 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 15352 KB Output is correct
2 Correct 69 ms 15352 KB Output is correct
3 Correct 48 ms 11128 KB Output is correct
4 Correct 10 ms 4608 KB Output is correct
5 Correct 9 ms 3944 KB Output is correct
6 Correct 17 ms 5632 KB Output is correct
7 Correct 2 ms 2688 KB Output is correct
8 Correct 33 ms 7676 KB Output is correct
9 Correct 43 ms 9464 KB Output is correct
10 Correct 2 ms 2816 KB Output is correct
11 Correct 69 ms 11896 KB Output is correct
12 Correct 88 ms 13688 KB Output is correct
13 Correct 3 ms 2816 KB Output is correct
14 Incorrect 2 ms 2688 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 15352 KB Output is correct
2 Correct 69 ms 15352 KB Output is correct
3 Correct 48 ms 11128 KB Output is correct
4 Correct 10 ms 4608 KB Output is correct
5 Correct 9 ms 3944 KB Output is correct
6 Correct 17 ms 5632 KB Output is correct
7 Correct 2 ms 2688 KB Output is correct
8 Correct 33 ms 7676 KB Output is correct
9 Correct 43 ms 9464 KB Output is correct
10 Correct 2 ms 2816 KB Output is correct
11 Correct 69 ms 11896 KB Output is correct
12 Correct 88 ms 13688 KB Output is correct
13 Correct 3 ms 2816 KB Output is correct
14 Incorrect 2 ms 2688 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 7928 KB Output is correct
2 Correct 32 ms 7936 KB Output is correct
3 Correct 30 ms 7928 KB Output is correct
4 Correct 31 ms 7936 KB Output is correct
5 Correct 31 ms 8056 KB Output is correct
6 Correct 33 ms 8692 KB Output is correct
7 Correct 38 ms 8312 KB Output is correct
8 Correct 31 ms 7800 KB Output is correct
9 Correct 31 ms 7804 KB Output is correct
10 Correct 34 ms 8052 KB Output is correct
11 Correct 2 ms 2688 KB Output is correct
12 Correct 7 ms 5752 KB Output is correct
13 Correct 8 ms 5880 KB Output is correct
14 Correct 7 ms 5624 KB Output is correct
15 Correct 7 ms 5752 KB Output is correct
16 Correct 7 ms 5624 KB Output is correct
17 Correct 7 ms 4856 KB Output is correct
18 Correct 8 ms 5880 KB Output is correct
19 Correct 7 ms 5624 KB Output is correct
20 Correct 3 ms 2688 KB Output is correct
21 Correct 2 ms 2688 KB Output is correct
22 Correct 2 ms 2816 KB Output is correct
23 Correct 9 ms 5624 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 15352 KB Output is correct
2 Correct 69 ms 15352 KB Output is correct
3 Correct 48 ms 11128 KB Output is correct
4 Correct 10 ms 4608 KB Output is correct
5 Correct 9 ms 3944 KB Output is correct
6 Correct 17 ms 5632 KB Output is correct
7 Correct 2 ms 2688 KB Output is correct
8 Correct 33 ms 7676 KB Output is correct
9 Correct 43 ms 9464 KB Output is correct
10 Correct 2 ms 2816 KB Output is correct
11 Correct 69 ms 11896 KB Output is correct
12 Correct 88 ms 13688 KB Output is correct
13 Correct 3 ms 2816 KB Output is correct
14 Correct 3 ms 2816 KB Output is correct
15 Correct 3 ms 2816 KB Output is correct
16 Incorrect 4 ms 2944 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 15352 KB Output is correct
2 Correct 69 ms 15352 KB Output is correct
3 Correct 48 ms 11128 KB Output is correct
4 Correct 10 ms 4608 KB Output is correct
5 Correct 9 ms 3944 KB Output is correct
6 Correct 17 ms 5632 KB Output is correct
7 Correct 2 ms 2688 KB Output is correct
8 Correct 33 ms 7676 KB Output is correct
9 Correct 43 ms 9464 KB Output is correct
10 Correct 2 ms 2816 KB Output is correct
11 Correct 69 ms 11896 KB Output is correct
12 Correct 88 ms 13688 KB Output is correct
13 Correct 3 ms 2816 KB Output is correct
14 Incorrect 2 ms 2688 KB Output isn't correct
15 Halted 0 ms 0 KB -