oj.uz

Submission #296591

# Submission time Handle Problem Language Result Execution time Memory
296591 2020-09-10T16:49:28 Z williamMBDK Dreaming (IOI13_dreaming) C++14
18 / 100
 113 ms 17928 KB 
#include<bits/stdc++.h>
#include "dreaming.h"
using namespace std;
int N, M;
vector<vector<pair<int,int>>> adj (1e5), distances (1e5);
vector<int> mxdist (1e5);
vector<vector<int>> getcomps(){
	vector<bool> v (N);
	vector<vector<int>> res;
	for(int i = 0; i < N; i++){
		if(!v[i]){
			queue<int> q;
			q.push(i);
			res.push_back({});
			while(!q.empty()){
				int curr = q.front(); q.pop();
				if(v[curr]) continue;
				v[curr] = 1;
				res[res.size() - 1].push_back(curr);
				for(auto e : adj[curr]) q.push(e.first);
			}
		}
	}
	return res;
}
int dfs1(int node, int p){
	for(int i = 0; i < adj[node].size(); i++){
		if(adj[node][i].first == p) continue;
		distances[node][i].first = dfs1(adj[node][i].first, node) + adj[node][i].second;
		distances[node][i].second = i;
	}
	sort(distances[node].rbegin(), distances[node].rend());
	if(distances[node].size() < 2) return 0; // right?
	return distances[node][0].first;
}
void dfs2(int node, int p, int mxp){
	if(p == -1){
		if(adj[node].size() > 0) mxdist[node] = distances[node][0].first;
		else mxdist[node] = 0;
	}else if(adj[node].size() == 1){
		mxdist[node] = mxp;	
	}else{
		mxdist[node] = max(mxp, distances[node][0].first); // right?
	}
	// cout << mxdist[node] << " " << node << endl;
	for(int i = 0; i < adj[node].size(); i++){
		if(adj[node][i].first == p) continue;
		int t = mxp;
		if(distances[node][0].second == i){
			if(distances[node].size() >= 3) t = max(t, distances[node][1].first);
		}else{
			t = max(t, distances[node][0].first); //right?
		}
		t += adj[node][i].second;
		dfs2(adj[node][i].first, node, t);
	}
}
int travelTime(int _N, int _M, int L, int A[], int B[], int T[]) {
	N = _N;
	M = _M;
	for(int i = 0; i < M; i++){
		adj[A[i]].push_back({B[i],T[i]});
		adj[B[i]].push_back({A[i],T[i]});
		distances[A[i]].push_back({-1,-1});
		distances[B[i]].push_back({-1,-1});
	}
	vector<vector<int>> components = getcomps();
	int C = components.size();
	vector<int> compdists (C, INT_MAX);
	for(int i = 0; i < C; i++){
		// cout << "root" << components[i][0] << endl;
		dfs1(components[i][0], -1);
		dfs2(components[i][0], -1, 0);
		for(int j = 0; j < components[i].size(); j++){
			compdists[i] = min(compdists[i], mxdist[components[i][j]]);
		}
	}
	sort(compdists.rbegin(), compdists.rend());
	if(C == 1){
		return compdists[0];
	}else if(C == 2){
		return L + compdists[0] + compdists[1];
	}else{
		return max(L + compdists[0] + compdists[1], 2 * L + compdists[1] + compdists[2]);
	}
}

Compilation message

dreaming.cpp: In function 'int dfs1(int, int)':
dreaming.cpp:27:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |  for(int i = 0; i < adj[node].size(); i++){
      |                 ~~^~~~~~~~~~~~~~~~~~
dreaming.cpp: In function 'void dfs2(int, int, int)':
dreaming.cpp:46:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |  for(int i = 0; i < adj[node].size(); i++){
      |                 ~~^~~~~~~~~~~~~~~~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:74:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |   for(int j = 0; j < components[i].size(); j++){
      |                  ~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 113 ms 17928 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 113 ms 17928 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 113 ms 17928 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 13776 KB Output is correct
2 Correct 75 ms 13884 KB Output is correct
3 Correct 92 ms 13740 KB Output is correct
4 Correct 82 ms 13868 KB Output is correct
5 Correct 70 ms 13740 KB Output is correct
6 Correct 106 ms 15628 KB Output is correct
7 Correct 101 ms 14212 KB Output is correct
8 Correct 81 ms 13612 KB Output is correct
9 Correct 72 ms 13612 KB Output is correct
10 Correct 87 ms 14148 KB Output is correct
11 Correct 6 ms 5436 KB Output is correct
12 Correct 39 ms 11288 KB Output is correct
13 Correct 31 ms 11312 KB Output is correct
14 Correct 38 ms 11304 KB Output is correct
15 Correct 30 ms 11356 KB Output is correct
16 Correct 33 ms 11304 KB Output is correct
17 Correct 26 ms 11304 KB Output is correct
18 Correct 40 ms 11344 KB Output is correct
19 Correct 33 ms 11312 KB Output is correct
20 Correct 4 ms 5480 KB Output is correct
21 Correct 5 ms 5376 KB Output is correct
22 Correct 6 ms 5632 KB Output is correct
23 Correct 35 ms 11304 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 113 ms 17928 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 113 ms 17928 KB Output isn't correct
2 Halted 0 ms 0 KB -