oj.uz

Submission #196851

# Submission time Handle Problem Language Result Execution time Memory
196851 2020-01-17T09:25:04 Z awlintqaa Dreaming (IOI13_dreaming) C++14
18 / 100
 535 ms 28608 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ppb pop_back
#define C continue
#define fi first
#define se second
typedef long long ll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pll> vpll;
typedef vector<pi> vpi;
#include "dreaming.h"
ll n,m,k;
vpll v[100009];
map<pll,ll>mp;
ll done[100009];
vll ret;
vpll all;
ll mx,id,z;
void dfs1(int node,int p,ll crnt){
        done[node]=1;
        if(crnt>=mx){
                mx=crnt;
                id=node;
        }
        for(auto u:v[node]){
                if(u.fi==p)C;
                dfs1(u.fi,node,crnt+u.se);
        }
}
void dfs2(int node,int p){
        done[node]=1;
        if(!z)ret.pb(node);
        if(node==id){
                z=1;
                return ;
        }
        for(auto u:v[node]){
                if(u.fi==p)C;
                dfs2(u.fi,node);
                if(z)return ;
        }
        if(!z)ret.ppb();
}
pll find(){
        vll X;
        X.resize((int)ret.size());
        ll crnt=0;
        for(int i=0;i<ret.size();i++){
                if(i)crnt+=mp[{ret[i],ret[i-1]}];
                X[i]=max(X[i],crnt);
        }
        crnt=0;
        ll timer=ret.size()-1;
        for(int i=0;i<ret.size();i++){
                if(i)crnt+=mp[{ret[i],ret[i-1]}];
                X[timer]=max(X[timer],crnt);
                timer--;
        }
        ll mn=1e9*2,id=0;
        for(int i=0;i<X.size();i++){
                if(X[i]<mn){
                        mn=X[i];
                        id=i;
                }
        }
        reverse(ret.begin(),ret.end());
        return {mn,ret[id]};
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
        n=N,m=M,k=L;
        for(int i=0;i<m;i++){
                int a=A[i],b=B[i],c=T[i];
                v[a].pb({b,c});
                v[b].pb({a,c});
                mp[{a,b}]=mp[{b,a}]=c;
        }
        for(int i=0;i<n;i++){
                if(done[i])C;
                mx=id=-1;
                z=0;
                ret.clear();
                dfs1(i,i,0);
                int xxx=id;
                mx=id=-1;
                dfs1(xxx,xxx,0);
                dfs2(xxx,xxx);
                all.pb(find());
        }
        sort(all.begin(),all.end());
        reverse(all.begin(),all.end());
        for(int i=1;i<all.size();i++){
                int a=all[i].se,b=all[0].se,c=L;
                v[a].pb({b,c});
                v[b].pb({a,c});
        }
        mx=id=-1;
        dfs1(0,0,0);
        mx=0;
        dfs1(id,id,0);
        return mx;
}

Compilation message

dreaming.cpp: In function 'pll find()':
dreaming.cpp:52:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<ret.size();i++){
                     ~^~~~~~~~~~~
dreaming.cpp:58:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<ret.size();i++){
                     ~^~~~~~~~~~~
dreaming.cpp:64:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<X.size();i++){
                     ~^~~~~~~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:95:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=1;i<all.size();i++){
                     ~^~~~~~~~~~~

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 535 ms 27544 KB Output is correct
2 Correct 361 ms 28608 KB Output is correct
3 Correct 208 ms 19952 KB Output is correct
4 Correct 32 ms 6520 KB Output is correct
5 Correct 26 ms 5240 KB Output is correct
6 Correct 63 ms 8668 KB Output is correct
7 Incorrect 6 ms 2808 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 535 ms 27544 KB Output is correct
2 Correct 361 ms 28608 KB Output is correct
3 Correct 208 ms 19952 KB Output is correct
4 Correct 32 ms 6520 KB Output is correct
5 Correct 26 ms 5240 KB Output is correct
6 Correct 63 ms 8668 KB Output is correct
7 Incorrect 6 ms 2808 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 535 ms 27544 KB Output is correct
2 Correct 361 ms 28608 KB Output is correct
3 Correct 208 ms 19952 KB Output is correct
4 Correct 32 ms 6520 KB Output is correct
5 Correct 26 ms 5240 KB Output is correct
6 Correct 63 ms 8668 KB Output is correct
7 Incorrect 6 ms 2808 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 13612 KB Output is correct
2 Correct 115 ms 13624 KB Output is correct
3 Correct 114 ms 13544 KB Output is correct
4 Correct 165 ms 13544 KB Output is correct
5 Correct 131 ms 13544 KB Output is correct
6 Correct 156 ms 15184 KB Output is correct
7 Correct 120 ms 14064 KB Output is correct
8 Correct 109 ms 13336 KB Output is correct
9 Correct 113 ms 13264 KB Output is correct
10 Correct 123 ms 13936 KB Output is correct
11 Correct 4 ms 2680 KB Output is correct
12 Correct 36 ms 9700 KB Output is correct
13 Correct 35 ms 9836 KB Output is correct
14 Correct 36 ms 9828 KB Output is correct
15 Correct 36 ms 9804 KB Output is correct
16 Correct 36 ms 9828 KB Output is correct
17 Correct 37 ms 9700 KB Output is correct
18 Correct 34 ms 9828 KB Output is correct
19 Correct 36 ms 9700 KB Output is correct
20 Correct 0 ms 2680 KB Output is correct
21 Correct 4 ms 2680 KB Output is correct
22 Correct 5 ms 2936 KB Output is correct
23 Correct 37 ms 9828 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 535 ms 27544 KB Output is correct
2 Correct 361 ms 28608 KB Output is correct
3 Correct 208 ms 19952 KB Output is correct
4 Correct 32 ms 6520 KB Output is correct
5 Correct 26 ms 5240 KB Output is correct
6 Correct 63 ms 8668 KB Output is correct
7 Incorrect 6 ms 2808 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 535 ms 27544 KB Output is correct
2 Correct 361 ms 28608 KB Output is correct
3 Correct 208 ms 19952 KB Output is correct
4 Correct 32 ms 6520 KB Output is correct
5 Correct 26 ms 5240 KB Output is correct
6 Correct 63 ms 8668 KB Output is correct
7 Incorrect 6 ms 2808 KB Output isn't correct
8 Halted 0 ms 0 KB -