oj.uz

Submission #114578

# Submission time Handle Problem Language Result Execution time Memory
114578 2019-06-01T20:51:01 Z ly20 Shortcut (IOI16_shortcut) C++14
0 / 100
 124 ms 149880 KB 
#include<bits/stdc++.h>
using namespace std;
#define debug(args...) //fprintf(stderr,args)
#include "shortcut.h"
const int MAXN=2123456;
const long long INF=11234567891234567;
vector<int> dm[MAXN],grafo[MAXN],peso[MAXN];
int marc[MAXN];
long long dist[MAXN],mx,idm;
set<pair<int,int> > s;
void dfs(int v)
{
	while(!s.empty())
	{
		int cur=(s.begin())->second;s.erase(s.begin());
		marc[cur]=1;
		for(int i=0;i<grafo[cur].size();i++)
		{
			int viz=grafo[cur][i],ps=peso[cur][i];
			if(marc[viz])continue;
			if(dist[viz]!=INF)s.erase(make_pair(dist[viz],viz));
			dist[viz]=min(dist[viz],dist[cur]+ps);
			s.insert(make_pair(dist[viz],viz));
		}
	}
}
long long find_shortcut(int n,vector<int> l,vector<int> d,int c)
{
	int tot=n;
	for(int i=0;i<n-1;i++)
	{
		grafo[i].push_back(i+1);grafo[i+1].push_back(i);
		peso[i].push_back(l[i]);peso[i+1].push_back(l[i+1]);
	}
	for(int i=0;i<n;i++)
	{
		if(d[i]!=0)
		{
			grafo[i].push_back(tot);grafo[tot].push_back(i);
			peso[i].push_back(d[i]);peso[tot].push_back(d[i]);
			tot++;
		}
	}
	debug("tot=%d\n",tot);
	long long resp=INF;
	for(int i=0;i<n;i++)
	{
		for(int j=i+1;j<n;j++)
		{
			grafo[i].push_back(j);grafo[j].push_back(i);
			peso[i].push_back(c);peso[j].push_back(c);
			idm=0;mx=0;
			for(int k=0;k<tot;k++)
			{
				dist[k]=INF;marc[k]=0;
			}
			dist[0]=0;
			s.insert(make_pair(dist[0],0));
			dfs(0);
			if(i==0 && j==6)
			{
				for(int i=0;i<tot;i++)printf("dist[%d]=%lld\n",i,dist[i]);
				debug("\n");
			}
			for(int k=0;k<tot;k++)
			{
				if(mx<=dist[k])
				{
					mx=dist[k];idm=k;
				}
			}
			for(int k=0;k<tot;k++)
			{
				dist[k]=INF;marc[k]=0;
			}
			dist[idm]=0;
			mx=0;
			s.insert(make_pair(dist[idm],idm));
			dfs(idm);
			for(int k=0;k<tot;k++)
			{
				mx=max(dist[k],mx);
			}
			if(mx==100)
			{
				for(int i=0;i<tot;i++)printf("dist[%d]=%lld\n",i,dist[i]);
				debug("\n");
			}
			resp=min(resp,mx);
			debug("%d %d\n",i,j);
			debug("%d %d\n",mx,idm);
			grafo[i].pop_back();grafo[j].pop_back();
			peso[i].pop_back();peso[j].pop_back();
		}
	}
	return resp;
}
/*int main()
{
	int n,c;
	vector<int> l,d;
	scanf("%d %d",&n,&c);
	int v;
	for(int i=0;i<n-1;i++)scanf("%d",&v),l.push_back(v);
	for(int i=0;i<n;i++)scanf("%d",&v),d.push_back(v);
	printf("%lld\n",find_shortcut(n,l,d,c));
}*/
/*
9 30
10 10 10 10 10 10 10 10
20 0 30 0 0 40 0 40 0
*/

Compilation message

shortcut.cpp: In function 'void dfs(int)':
shortcut.cpp:17:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<grafo[cur].size();i++)
               ~^~~~~~~~~~~~~~~~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 124 ms 149880 KB Secret is incorrect!
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 124 ms 149880 KB Secret is incorrect!
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 124 ms 149880 KB Secret is incorrect!
2 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 124 ms 149880 KB Secret is incorrect!
2 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 124 ms 149880 KB Secret is incorrect!
2 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 124 ms 149880 KB Secret is incorrect!
2 Halted 0 ms 0 KB -

Subtask #7
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 124 ms 149880 KB Secret is incorrect!
2 Halted 0 ms 0 KB -

Subtask #8
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 124 ms 149880 KB Secret is incorrect!
2 Halted 0 ms 0 KB -