oj.uz

답안 #571274

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
571274 2022-06-01T15:53:41 Z beaconmc 꿈 (IOI13_dreaming) C++14
0 / 100
 1000 ms 14780 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());


	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[5] = {95, 98, 64, 49, 52}, b[5] = {73, 34, 7, 55, 43}, c[5] = {1667, 3851, 2414, 7129, 4781};
// 	cout << travelTime(100, 5, 10000,a,b,c);


// }

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

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1064 ms 14780 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 5076 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1064 ms 14780 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 220 ms 10804 KB Output is correct
2 Correct 243 ms 11188 KB Output is correct
3 Correct 267 ms 11072 KB Output is correct
4 Correct 218 ms 11088 KB Output is correct
5 Correct 286 ms 11236 KB Output is correct
6 Correct 236 ms 11900 KB Output is correct
7 Correct 230 ms 11408 KB Output is correct
8 Correct 214 ms 11092 KB Output is correct
9 Correct 199 ms 11016 KB Output is correct
10 Correct 224 ms 11312 KB Output is correct
11 Correct 3 ms 5012 KB Output is correct
12 Correct 38 ms 10128 KB Output is correct
13 Correct 39 ms 10212 KB Output is correct
14 Correct 38 ms 10128 KB Output is correct
15 Correct 38 ms 10152 KB Output is correct
16 Correct 38 ms 10060 KB Output is correct
17 Correct 36 ms 10056 KB Output is correct
18 Correct 42 ms 10184 KB Output is correct
19 Correct 38 ms 10184 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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 5076 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1064 ms 14780 KB Time limit exceeded
2 Halted 0 ms 0 KB -