oj.uz

Submission #305747

# Submission time Handle Problem Language Result Execution time Memory
305747 2020-09-23T22:35:42 Z sofapuden Dreaming (IOI13_dreaming) C++14
14 / 100
 77 ms 15092 KB 
    #include "dreaming.h"
    #include <bits/stdc++.h>
     
    using namespace std;
    vector<vector<pair<int,int>>> gri;
    vector<int> dis;
    vector<int> dep;
    vector<int> used;
    int jic = 0;
    int ans = 0;
    int y;
     
    int dfs2(int x, int p, int d){
    	int bes = 0;
    	int bes2 = 0;
    	for(int i = 0; i < gri[x].size(); ++i){
    		if(gri[x][i].first == p)continue;
    		int cur = dfs2(gri[x][i].first, x, d+gri[x][i].second);
    		if(bes < cur)swap(cur, bes);
    		if(bes2 < cur)swap(cur, bes2);
    	}
    	ans = max(ans, max(bes+bes2-2*d, d));
    	return max(d, bes);
    	
    }
    int dfs(int x, int p){
    	used[x] = 1;
    	int s = 0;
    	for(int i = 0; i < (int)gri[x].size(); ++i){
    		int z = 0;
    		if(gri[x][i].first != p)z = dfs(gri[x][i].first,x)+gri[x][i].second;
    		dep.push_back(z);
    		s+=z;
    	}
    	return s;
    }
    void find(int ind){
    	if(!gri[ind].size()){dis.push_back(0);return;}
    	dep.clear();
    	y = dfs(ind,ind);
    	int lll = dfs2(ind,ind,0);
    	jic = max(jic,lll);
    	int best = INT_MAX;
    	for(int i = 0; i < (int)dep.size(); ++i){
    		best = min(best, max(y-dep[i],dep[i]));
    	}
    	dis.push_back(best);	
    }
     
    int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
		if(N == 1)return 0;
		if(N == 2)return (M ? L : T[0]);
        used.resize(N,0);
        gri.resize(N);
        for(int i = 0; i < M; ++i){
    		gri[A[i]].push_back({B[i],T[i]});
    		gri[B[i]].push_back({A[i],T[i]});
    	}
    	for(int i = 0; i < N; ++i){
    		if(!used[i] && gri[i].size() == 1){
    			find(i);
    		}
    	}
    	sort(dis.rbegin(),dis.rend());
    	if(dis.size() >= 3){
			return max(jic,max(dis[0]+L+dis[1],dis[1]+dis[2]+2*L));
		}
		if(dis.size() == 2){
			return max(jic,dis[0]+L+dis[1]);
		}
		return jic;
    }

Compilation message

dreaming.cpp: In function 'int dfs2(int, int, int)':
dreaming.cpp:16:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |      for(int i = 0; i < gri[x].size(); ++i){
      |                     ~~^~~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 15092 KB Output is correct
2 Correct 65 ms 14964 KB Output is correct
3 Correct 42 ms 9852 KB Output is correct
4 Correct 9 ms 2560 KB Output is correct
5 Correct 8 ms 1536 KB Output is correct
6 Correct 15 ms 3712 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 30 ms 5368 KB Output is correct
9 Correct 39 ms 7672 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 77 ms 9720 KB Output is correct
12 Correct 75 ms 12528 KB Output is correct
13 Correct 1 ms 384 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 15092 KB Output is correct
2 Correct 65 ms 14964 KB Output is correct
3 Correct 42 ms 9852 KB Output is correct
4 Correct 9 ms 2560 KB Output is correct
5 Correct 8 ms 1536 KB Output is correct
6 Correct 15 ms 3712 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 30 ms 5368 KB Output is correct
9 Correct 39 ms 7672 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 77 ms 9720 KB Output is correct
12 Correct 75 ms 12528 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Incorrect 1 ms 384 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 15092 KB Output is correct
2 Correct 65 ms 14964 KB Output is correct
3 Correct 42 ms 9852 KB Output is correct
4 Correct 9 ms 2560 KB Output is correct
5 Correct 8 ms 1536 KB Output is correct
6 Correct 15 ms 3712 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 30 ms 5368 KB Output is correct
9 Correct 39 ms 7672 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 77 ms 9720 KB Output is correct
12 Correct 75 ms 12528 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Incorrect 1 ms 384 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 5504 KB Output is correct
2 Correct 29 ms 5504 KB Output is correct
3 Correct 30 ms 5496 KB Output is correct
4 Correct 26 ms 5504 KB Output is correct
5 Correct 25 ms 5496 KB Output is correct
6 Correct 26 ms 5888 KB Output is correct
7 Correct 27 ms 5752 KB Output is correct
8 Correct 27 ms 5408 KB Output is correct
9 Correct 25 ms 5368 KB Output is correct
10 Correct 27 ms 5624 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 3 ms 3072 KB Output is correct
13 Correct 3 ms 3072 KB Output is correct
14 Correct 3 ms 3072 KB Output is correct
15 Correct 3 ms 3072 KB Output is correct
16 Correct 3 ms 3072 KB Output is correct
17 Correct 3 ms 3072 KB Output is correct
18 Correct 3 ms 3072 KB Output is correct
19 Correct 3 ms 3072 KB Output is correct
20 Correct 0 ms 256 KB Output is correct
21 Incorrect 1 ms 256 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 15092 KB Output is correct
2 Correct 65 ms 14964 KB Output is correct
3 Correct 42 ms 9852 KB Output is correct
4 Correct 9 ms 2560 KB Output is correct
5 Correct 8 ms 1536 KB Output is correct
6 Correct 15 ms 3712 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 30 ms 5368 KB Output is correct
9 Correct 39 ms 7672 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 77 ms 9720 KB Output is correct
12 Correct 75 ms 12528 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Incorrect 1 ms 384 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 15092 KB Output is correct
2 Correct 65 ms 14964 KB Output is correct
3 Correct 42 ms 9852 KB Output is correct
4 Correct 9 ms 2560 KB Output is correct
5 Correct 8 ms 1536 KB Output is correct
6 Correct 15 ms 3712 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 30 ms 5368 KB Output is correct
9 Correct 39 ms 7672 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 77 ms 9720 KB Output is correct
12 Correct 75 ms 12528 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Incorrect 1 ms 384 KB Output isn't correct
15 Halted 0 ms 0 KB -