| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 133026 |
2019-07-20T05:18:18 Z |
wzy |
Shortcut (IOI16_shortcut) |
C++11 |
|
2 ms |
504 KB |
// cancer problem D:
#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,long long>
#define F first
#define S second
#define pb push_back
const int N = 3003;
typedef long long ll;
ll dist[N][N];
vector<pii> adj[N];
ll diametro[N][N];
int n;
vector<int> passa;
int pai[N];
ll dp[N];
ll g[N];
int cx[N];
void fill_dist(int i , int p , int d , int r){
dist[r][i] = d;
for(auto w : adj[i]){
if(p != w.F){
fill_dist(w.F , i , d +w.S , r);
}
}
}
void diam(int x , int p , int bl1 , int bl2 ){
for(auto w : adj[x]){
if(w.F == p || w.F == bl1 || w.F == bl2) continue;
diam(w.F , x , bl1 , bl2);
dp[x] = max(max(dp[w.F] , g[x] + w.S + g[w.F]) , dp[x]);
g[x] = max(g[w.F] + w.S , g[x]);
}
}
void dfs(int x , int p){
pai[x] = p;
for(auto w : adj[x]){
if(w.F != p){
dfs(w.F , x);
}
}
}
ll solve(int x , int y , int c){
dfs(x , -1);
int u = y;
vector<pii> v;
for(int i = 0 ; i < n ; i ++){
cx[i] = 0 ;
g[i] = 0 , dp[i] = 0;
}
while(u != -1){
int d = 0;
if(u == x){
d = 0;
}
else{
d = dist[pai[u]][u];
}
v.push_back(pii(u , d));
u = pai[u];
}
reverse(v.begin() ,v.end());
ll ans = 0;
for(int i = 0 ; i < v.size() ;i ++){
int x1 = v[(i+1)%v.size()].F;
int x2 = v[(i-1 + v.size())%v.size()].F;
int L = -1;
for(auto w : adj[v[i].F]){
if(w.F != x1 && w.F != x2){
L = w.F;
}
}
if(L != -1){
diam(v[i].F , -1 , x1 , x2);
ans = max(ans , dp[v[i].F]);
}
if(L != -1)
cx[v[i].F] = g[v[i].F];
if(i > 0){
v[i].S += v[i-1].S;
}
}
int r = 0;
int S = v.back().S + c;
for(int i = 0 ; i < v.size() ; i ++){
if(r%v.size() == i){
r++;
}
while((r+1)%v.size() != i && (min(S - abs(v[i].S - v[r%v.size()].S) , abs(v[i].S - v[(r)%v.size()].S)) + cx[v[r%v.size()].F] + cx[v[i].F]) < (min(S - abs(v[i].S - v[(r+1)%v.size()].S) , abs(v[i].S - v[(r+1)%v.size()].S)) + cx[v[(r+1)%v.size()].F] + cx[v[i].F]) ){
r++;
ans = max(ans , min(S - abs(v[i].S - v[r%v.size()].S) , abs(v[i].S - v[(r)%v.size()].S)) + cx[v[r%v.size()].F] + cx[v[i].F]);
}
ans = max(ans , min(S - abs(v[i].S - v[r%v.size()].S) , abs(v[i].S - v[(r)%v.size()].S)) + cx[v[r%v.size()].F] + cx[v[i].F]);
}
return ans;
}
long long find_shortcut(int nx, std::vector<int> l, std::vector<int> d, int c)
{
n = nx;
for(int i = 0 ; i < n-1; i ++){
adj[i].push_back(pii(i+1 , l[i]));
adj[i+1].push_back(pii(i , l[i]));
}
for(int i = 0 ; i < nx; i ++){
if(d[i] != 0){
n;
adj[n].push_back(pii(i, d[i]));
adj[i].push_back(pii(n , d[i]));
n++;
}
}
for(int i = 0 ; i < n; i ++){
for(int j = 0 ; j < n ; j ++) dist[i][j] = (ll) 1e18;
dist[i][i] = 0;
fill_dist(i , -1 , 0 , i);
}
ll p = 0;
for(int i = 0 ; i < n ; i ++)
for(int j = 0 ; j < n ; j ++){
p = max(p , dist[i][j]);
}
// cout<<p<<endl;
for(int i = 0 ; i < nx ; i ++){
for(int j = i+1 ; j < nx ; j ++){
p = min(p , solve(i, j , c));
// cout<<solve(i,j,c)<<" " <<i <<" " <<j <<" " << endl;
}
}
return p;
}
Compilation message
shortcut.cpp: In function 'll solve(int, int, int)':
shortcut.cpp:69:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0 ; i < v.size() ;i ++){
~~^~~~~~~~~~
shortcut.cpp:91:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0 ; i < v.size() ; i ++){
~~^~~~~~~~~~
shortcut.cpp:92:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(r%v.size() == i){
~~~~~~~~~~~^~~~
shortcut.cpp:95:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while((r+1)%v.size() != i && (min(S - abs(v[i].S - v[r%v.size()].S) , abs(v[i].S - v[(r)%v.size()].S)) + cx[v[r%v.size()].F] + cx[v[i].F]) < (min(S - abs(v[i].S - v[(r+1)%v.size()].S) , abs(v[i].S - v[(r+1)%v.size()].S)) + cx[v[(r+1)%v.size()].F] + cx[v[i].F]) ){
~~~~~~~~~~~~~~~^~~~
shortcut.cpp: In function 'long long int find_shortcut(int, std::vector<int>, std::vector<int>, int)':
shortcut.cpp:114:5: warning: statement has no effect [-Wunused-value]
n;
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
448 KB |
n = 4, 80 is a correct answer |
| 2 |
Incorrect |
2 ms |
504 KB |
n = 9, incorrect answer: jury 110 vs contestant 100 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
448 KB |
n = 4, 80 is a correct answer |
| 2 |
Incorrect |
2 ms |
504 KB |
n = 9, incorrect answer: jury 110 vs contestant 100 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
448 KB |
n = 4, 80 is a correct answer |
| 2 |
Incorrect |
2 ms |
504 KB |
n = 9, incorrect answer: jury 110 vs contestant 100 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
448 KB |
n = 4, 80 is a correct answer |
| 2 |
Incorrect |
2 ms |
504 KB |
n = 9, incorrect answer: jury 110 vs contestant 100 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
448 KB |
n = 4, 80 is a correct answer |
| 2 |
Incorrect |
2 ms |
504 KB |
n = 9, incorrect answer: jury 110 vs contestant 100 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
448 KB |
n = 4, 80 is a correct answer |
| 2 |
Incorrect |
2 ms |
504 KB |
n = 9, incorrect answer: jury 110 vs contestant 100 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
448 KB |
n = 4, 80 is a correct answer |
| 2 |
Incorrect |
2 ms |
504 KB |
n = 9, incorrect answer: jury 110 vs contestant 100 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
448 KB |
n = 4, 80 is a correct answer |
| 2 |
Incorrect |
2 ms |
504 KB |
n = 9, incorrect answer: jury 110 vs contestant 100 |
| 3 |
Halted |
0 ms |
0 KB |
- |
