Submission #776343

#	Time	Username	Problem	Language	Result	Execution time	Memory
776343		tolbi	Dreaming (IOI13_dreaming)	C++17	100 / 100	52 ms	10708 KiB

dreaming

#pragma optimize("Bismillahirrahmanirrahim")
//█▀█─█──█──█▀█─█─█
//█▄█─█──█──█▄█─█■█
//█─█─█▄─█▄─█─█─█─█
//Allahuekber
//ahmet23 orz...
//FatihSultanMehmedHan
//YavuzSultanSelimHan
//AbdulhamidHan
//Sani buyuk Osman Pasa Plevneden cikmam diyor.
#define author tolbi
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define sortarr(x) sort(x.begin(), x.end())
#define sortrarr(x) sort(x.rbegin(), x.rend())
#define coutarr(x) for (auto &it : x) cout<<it<<" ";cout<<endl;
#define rev(x) reverse(x.begin(), x.end())
#define tol(bi) (1LL<<((int)(bi)))
mt19937 ayahya(chrono::high_resolution_clock().now().time_since_epoch().count());
typedef long long ll;
const ll MOD = 1e9+7;
const ll INF = 1e18;
#include "dreaming.h"
int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
	vector<vector<pair<int,int>>> arr(n);
	for (int i = 0; i < m; i++){
		arr[a[i]].push_back({b[i],t[i]});
		arr[b[i]].push_back({a[i],t[i]});
	}
	vector<int> adp(n,-1);
	vector<int> bdp(n,-1);
	vector<bool> vis(n,false);
	int an,bn;
	vector<int> x;
	int ans = 0;
	queue<pair<pair<int,int>,int>> q;
	for (int src = 0; src < n; src++){
		if (vis[src]) continue;
		q.push({{src,-1},0});
		vector<int> gez;
		bn=src;
		while (q.size()){
			int node = q.front().first.first;
			int lnode = q.front().first.second;
			int w = q.front().second;
			bdp[node]=w;
			vis[node]=true;
			gez.push_back(node);
			q.pop();
			for (int i = 0; i < arr[node].size(); i++){
				if (arr[node][i].first==lnode) continue;
				q.push({{arr[node][i].first,node},w+arr[node][i].second});
			}
		}
		an=src;
		for (int i = 0; i < gez.size(); i++){
			if (bdp[gez[i]]>bdp[an]) an = gez[i];
		}
		q.push({{an,-1},0});
		while (q.size()){
			int node = q.front().first.first;
			int lnode = q.front().first.second;
			int w = q.front().second;
			adp[node]=w;
			q.pop();
			for (int i = 0; i < arr[node].size(); i++){
				if (arr[node][i].first==lnode) continue;
				q.push({{arr[node][i].first,node},w+arr[node][i].second});
			}
		}
		bn=src;
		for (int i = 0; i < gez.size(); i++){
			if (adp[gez[i]]>adp[bn]) bn = gez[i];
		}

		q.push({{bn,-1},0});
		while (q.size()){
			int node = q.front().first.first;
			int lnode = q.front().first.second;
			int w = q.front().second;
			bdp[node]=w;
			q.pop();
			for (int i = 0; i < arr[node].size(); i++){
				if (arr[node][i].first==lnode) continue;
				q.push({{arr[node][i].first,node},w+arr[node][i].second});
			}
		}
		ans=max(ans,adp[bn]);
		int kk = adp[bn];
		for (int i = 0; i < gez.size(); i++){
			kk=min(kk,max(adp[gez[i]],bdp[gez[i]]));
		}
		x.push_back(kk);
	}
	sortrarr(x);
	if (x.size()>=2) ans=max(ans,x[0]+x[1]+l);
	if (x.size()>=3) ans=max(ans,x[1]+x[2]+l*2);
	return ans;
}

Compilation message (stderr)

dreaming.cpp:1: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    1 | #pragma optimize("Bismillahirrahmanirrahim")
      | 
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:51:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |    for (int i = 0; i < arr[node].size(); i++){
      |                    ~~^~~~~~~~~~~~~~~~~~
dreaming.cpp:57:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |   for (int i = 0; i < gez.size(); i++){
      |                   ~~^~~~~~~~~~~~
dreaming.cpp:67:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |    for (int i = 0; i < arr[node].size(); i++){
      |                    ~~^~~~~~~~~~~~~~~~~~
dreaming.cpp:73:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |   for (int i = 0; i < gez.size(); i++){
      |                   ~~^~~~~~~~~~~~
dreaming.cpp:84:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |    for (int i = 0; i < arr[node].size(); i++){
      |                    ~~^~~~~~~~~~~~~~~~~~
dreaming.cpp:91:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |   for (int i = 0; i < gez.size(); i++){
      |                   ~~^~~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 10 / 10
• Subtask 3: 23 / 23
• Subtask 4: 18 / 18
• Subtask 5: 12 / 12
• Subtask 6: 23 / 23