| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 114579 |
2019-06-01T20:51:41 Z |
ly20 |
Shortcut (IOI16_shortcut) |
C++14 |
|
121 ms |
150068 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++)debug("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++)debug("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++)
~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
119 ms |
149880 KB |
n = 4, 80 is a correct answer |
| 2 |
Correct |
118 ms |
149880 KB |
n = 9, 110 is a correct answer |
| 3 |
Correct |
121 ms |
150068 KB |
n = 4, 21 is a correct answer |
| 4 |
Incorrect |
119 ms |
149864 KB |
n = 3, incorrect answer: jury 4 vs contestant 3 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
119 ms |
149880 KB |
n = 4, 80 is a correct answer |
| 2 |
Correct |
118 ms |
149880 KB |
n = 9, 110 is a correct answer |
| 3 |
Correct |
121 ms |
150068 KB |
n = 4, 21 is a correct answer |
| 4 |
Incorrect |
119 ms |
149864 KB |
n = 3, incorrect answer: jury 4 vs contestant 3 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
119 ms |
149880 KB |
n = 4, 80 is a correct answer |
| 2 |
Correct |
118 ms |
149880 KB |
n = 9, 110 is a correct answer |
| 3 |
Correct |
121 ms |
150068 KB |
n = 4, 21 is a correct answer |
| 4 |
Incorrect |
119 ms |
149864 KB |
n = 3, incorrect answer: jury 4 vs contestant 3 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
119 ms |
149880 KB |
n = 4, 80 is a correct answer |
| 2 |
Correct |
118 ms |
149880 KB |
n = 9, 110 is a correct answer |
| 3 |
Correct |
121 ms |
150068 KB |
n = 4, 21 is a correct answer |
| 4 |
Incorrect |
119 ms |
149864 KB |
n = 3, incorrect answer: jury 4 vs contestant 3 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
119 ms |
149880 KB |
n = 4, 80 is a correct answer |
| 2 |
Correct |
118 ms |
149880 KB |
n = 9, 110 is a correct answer |
| 3 |
Correct |
121 ms |
150068 KB |
n = 4, 21 is a correct answer |
| 4 |
Incorrect |
119 ms |
149864 KB |
n = 3, incorrect answer: jury 4 vs contestant 3 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
119 ms |
149880 KB |
n = 4, 80 is a correct answer |
| 2 |
Correct |
118 ms |
149880 KB |
n = 9, 110 is a correct answer |
| 3 |
Correct |
121 ms |
150068 KB |
n = 4, 21 is a correct answer |
| 4 |
Incorrect |
119 ms |
149864 KB |
n = 3, incorrect answer: jury 4 vs contestant 3 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
119 ms |
149880 KB |
n = 4, 80 is a correct answer |
| 2 |
Correct |
118 ms |
149880 KB |
n = 9, 110 is a correct answer |
| 3 |
Correct |
121 ms |
150068 KB |
n = 4, 21 is a correct answer |
| 4 |
Incorrect |
119 ms |
149864 KB |
n = 3, incorrect answer: jury 4 vs contestant 3 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
119 ms |
149880 KB |
n = 4, 80 is a correct answer |
| 2 |
Correct |
118 ms |
149880 KB |
n = 9, 110 is a correct answer |
| 3 |
Correct |
121 ms |
150068 KB |
n = 4, 21 is a correct answer |
| 4 |
Incorrect |
119 ms |
149864 KB |
n = 3, incorrect answer: jury 4 vs contestant 3 |
