oj.uz

Submission #571285

# Submission time Handle Problem Language Result Execution time Memory
571285 2022-06-01T16:09:32 Z beaconmc Dreaming (IOI13_dreaming) C++14
0 / 100
 1000 ms 14256 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
typedef long long ll;
#define FOR(i,x,y) for(ll i=x; i<y; i++)
#define FORNEG(i,x,y) for(ll i=x; i>y; i--)
#define double long double
#include "dreaming.h"

using namespace std;


ll cc[100005];

ll find(ll a){
    while (a!=cc[a]) cc[a] = cc[cc[a]], a = cc[a];
    return a;
}
void unite(ll a,ll b){
    cc[find(a)] = find(b);
}


vector<pair<ll, ll>> edges[100005];
vector<ll> sussies[100005];


int sus(vector<ll> a){
	if (a.size()==1) return 0;

	bool visited[100005];
	FOR(i,0,100004) visited[i] = 1;

	for (auto&i : a){
		visited[i] = 0;
	}
	vector<vector<ll>> stack;
	ll maxi = 0;
	vector<ll> path;

	stack.push_back({0,a[0]});
	visited[a[0]] = 1;

	while (stack.size()){
		vector<ll> temp;

		vector<ll> node = stack[stack.size()-1];

		stack.pop_back();

		if (maxi < node[0]) path = node, maxi = node[0];


		for (auto&i : edges[node[node.size()-1]]){
			if (!visited[i.first]){
				visited[i.first] = 1;
				temp = node;
				temp[0] += i.second;
				temp.push_back(i.first);
				stack.push_back(temp);
			}
		}
	}


	ll realsus = path[path.size()-1];


	FOR(i,0,100004) visited[i] = 1;

	for (auto&i : a){
		visited[i] = 0;
	}
	stack.clear();
	maxi = 0;
	path.clear();
	stack.push_back({0,0,realsus});
	visited[realsus] = 1;



	while (stack.size()){
		vector<ll> temp;

		vector<ll> node = stack[stack.size()-1];
		stack.pop_back();

		if (maxi < node[0]) path = node, maxi = node[0];

		for (auto&i : edges[node[node.size()-1]]){
			if (!visited[i.first]){
				visited[i.first] = 1;
				temp = node;
				temp.pop_back();
				temp[0] += i.second;
				temp.push_back(i.second);
				temp.push_back(i.first);
				stack.push_back(temp);
			}
		}
	}

	ll mini = 1000000000;
	ll cur = 0;




	FOR(i,1,path.size()-1){
		cur += path[i];
		mini = min(mini, max(path[0]-cur, cur));
	}


	return mini;

}


int travelTime(int n, int m, int L, int a[], int b[], int t[]){
	FOR(i,0,n) cc[i] = i;

	FOR(i,0,m){
		edges[a[i]].push_back({b[i], t[i]});
		edges[b[i]].push_back({a[i], t[i]});
	}

	FOR(i,0,n){
		for (auto&j : edges[i]){
			unite(i, j.first);
		}
	}

	FOR(i,0,n){
		sussies[find(i)].push_back(i);
	}
	vector<ll> kindasus;


	for (auto&i : sussies){
		if (i.size()==0) continue;
		kindasus.push_back(sus(i));
	}

	sort(kindasus.begin(), kindasus.end());

	// for (auto&i : kindasus){
	// 	cout << i << endl;
	// }

	if (kindasus.size()==2){
		return kindasus[kindasus.size()-1] + kindasus[kindasus.size()-2] + L;
	}


	return max(kindasus[kindasus.size()-2] + kindasus[kindasus.size()-3] + 2*L, kindasus[kindasus.size()-1] + kindasus[kindasus.size()-2] + L);

}

// int main(){
// 	int a,b,c;
// 	cin>> a >> b >> c;

// 	int d[b], e[b], f[b];

// 	FOR(i,0,b){
// 		cin >> d[i] >> e[i] >>f[i];
// 	}
// 	cout << travelTime(a,b,c,d,e,f);


// }

Compilation message

dreaming.cpp: In function 'int sus(std::vector<long long int>)':
dreaming.cpp:4:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define FOR(i,x,y) for(ll i=x; i<y; i++)
......
  108 |  FOR(i,1,path.size()-1){
      |      ~~~~~~~~~~~~~~~~~           
dreaming.cpp:108:2: note: in expansion of macro 'FOR'
  108 |  FOR(i,1,path.size()-1){
      |  ^~~

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1095 ms 14256 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1095 ms 14256 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 223 ms 10696 KB Output is correct
2 Correct 255 ms 10664 KB Output is correct
3 Correct 212 ms 10660 KB Output is correct
4 Correct 220 ms 10832 KB Output is correct
5 Correct 236 ms 10840 KB Output is correct
6 Correct 224 ms 11560 KB Output is correct
7 Correct 243 ms 11132 KB Output is correct
8 Correct 208 ms 10572 KB Output is correct
9 Correct 252 ms 10640 KB Output is correct
10 Correct 232 ms 10832 KB Output is correct
11 Correct 4 ms 5076 KB Output is correct
12 Correct 40 ms 10136 KB Output is correct
13 Correct 42 ms 10188 KB Output is correct
14 Correct 42 ms 10160 KB Output is correct
15 Correct 40 ms 10104 KB Output is correct
16 Correct 38 ms 10160 KB Output is correct
17 Correct 42 ms 10056 KB Output is correct
18 Correct 44 ms 10116 KB Output is correct
19 Correct 42 ms 10192 KB Output is correct
20 Incorrect 3 ms 5076 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1095 ms 14256 KB Time limit exceeded
2 Halted 0 ms 0 KB -