oj.uz

Submission #297857

# Submission time Handle Problem Language Result Execution time Memory
297857 2020-09-12T05:25:19 Z Bill_00 Dreaming (IOI13_dreaming) C++14
32 / 100
 86 ms 14472 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];
long long go[100001];
vector<pair<long long,long long> >adj[100001];
void dfsd(long long u,long v,long long w){
	cost[u]=w;
	if(w>path){
		id=u;
		path=w;
	}
	go[u]=v;
	for(long long i=0;i<adj[u].size();i++){
		long long f=adj[u][i].ff;
		long long s=adj[u][i].ss;
		if(f!=v){
			dfsd(f,u,w+s);
		}
	}
	
}
void dfs(long long u,long long v,long long w){
	vis[u]=1;
	if(w>p){
		id=u;
		p=w;
	}
	for(long long i=0;i<adj[u].size();i++){
		long long 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(long long i=0;i<m;i++){
		adj[a[i]].pb(mp((long long)b[i],(long long)t[i]));
		adj[b[i]].pb(mp((long long)a[i],(long long)t[i]));
	}
    for(long long 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(long long int, long int, long long int)':
dreaming.cpp:20:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |  for(long long i=0;i<adj[u].size();i++){
      |                    ~^~~~~~~~~~~~~~
dreaming.cpp: In function 'void dfs(long long int, long long int, long long int)':
dreaming.cpp:35:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |  for(long long i=0;i<adj[u].size();i++){
      |                    ~^~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 14456 KB Output is correct
2 Correct 66 ms 14472 KB Output is correct
3 Correct 43 ms 10360 KB Output is correct
4 Correct 10 ms 4352 KB Output is correct
5 Correct 8 ms 3840 KB Output is correct
6 Correct 19 ms 5504 KB Output is correct
7 Correct 2 ms 2688 KB Output is correct
8 Correct 38 ms 7404 KB Output is correct
9 Correct 45 ms 8952 KB Output is correct
10 Correct 2 ms 2816 KB Output is correct
11 Correct 72 ms 11128 KB Output is correct
12 Correct 86 ms 12920 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 64 ms 14456 KB Output is correct
2 Correct 66 ms 14472 KB Output is correct
3 Correct 43 ms 10360 KB Output is correct
4 Correct 10 ms 4352 KB Output is correct
5 Correct 8 ms 3840 KB Output is correct
6 Correct 19 ms 5504 KB Output is correct
7 Correct 2 ms 2688 KB Output is correct
8 Correct 38 ms 7404 KB Output is correct
9 Correct 45 ms 8952 KB Output is correct
10 Correct 2 ms 2816 KB Output is correct
11 Correct 72 ms 11128 KB Output is correct
12 Correct 86 ms 12920 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 64 ms 14456 KB Output is correct
2 Correct 66 ms 14472 KB Output is correct
3 Correct 43 ms 10360 KB Output is correct
4 Correct 10 ms 4352 KB Output is correct
5 Correct 8 ms 3840 KB Output is correct
6 Correct 19 ms 5504 KB Output is correct
7 Correct 2 ms 2688 KB Output is correct
8 Correct 38 ms 7404 KB Output is correct
9 Correct 45 ms 8952 KB Output is correct
10 Correct 2 ms 2816 KB Output is correct
11 Correct 72 ms 11128 KB Output is correct
12 Correct 86 ms 12920 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 7860 KB Output is correct
2 Correct 33 ms 7936 KB Output is correct
3 Correct 33 ms 7800 KB Output is correct
4 Correct 32 ms 7928 KB Output is correct
5 Correct 32 ms 7928 KB Output is correct
6 Correct 33 ms 8828 KB Output is correct
7 Correct 32 ms 8056 KB Output is correct
8 Correct 30 ms 7800 KB Output is correct
9 Correct 28 ms 7796 KB Output is correct
10 Correct 31 ms 8052 KB Output is correct
11 Correct 2 ms 2688 KB Output is correct
12 Correct 7 ms 6008 KB Output is correct
13 Correct 7 ms 6136 KB Output is correct
14 Correct 7 ms 6008 KB Output is correct
15 Correct 9 ms 6008 KB Output is correct
16 Correct 8 ms 5880 KB Output is correct
17 Correct 6 ms 4984 KB Output is correct
18 Correct 8 ms 6264 KB Output is correct
19 Correct 7 ms 5880 KB Output is correct
20 Correct 2 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 7 ms 6008 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 14456 KB Output is correct
2 Correct 66 ms 14472 KB Output is correct
3 Correct 43 ms 10360 KB Output is correct
4 Correct 10 ms 4352 KB Output is correct
5 Correct 8 ms 3840 KB Output is correct
6 Correct 19 ms 5504 KB Output is correct
7 Correct 2 ms 2688 KB Output is correct
8 Correct 38 ms 7404 KB Output is correct
9 Correct 45 ms 8952 KB Output is correct
10 Correct 2 ms 2816 KB Output is correct
11 Correct 72 ms 11128 KB Output is correct
12 Correct 86 ms 12920 KB Output is correct
13 Correct 3 ms 2816 KB Output is correct
14 Correct 2 ms 2816 KB Output is correct
15 Correct 3 ms 2816 KB Output is correct
16 Incorrect 3 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 64 ms 14456 KB Output is correct
2 Correct 66 ms 14472 KB Output is correct
3 Correct 43 ms 10360 KB Output is correct
4 Correct 10 ms 4352 KB Output is correct
5 Correct 8 ms 3840 KB Output is correct
6 Correct 19 ms 5504 KB Output is correct
7 Correct 2 ms 2688 KB Output is correct
8 Correct 38 ms 7404 KB Output is correct
9 Correct 45 ms 8952 KB Output is correct
10 Correct 2 ms 2816 KB Output is correct
11 Correct 72 ms 11128 KB Output is correct
12 Correct 86 ms 12920 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 -