oj.uz

Submission #196857

# Submission time Handle Problem Language Result Execution time Memory
196857 2020-01-17T10:07:57 Z awlintqaa Dreaming (IOI13_dreaming) C++14
18 / 100
 1000 ms 11196 KB 
#define fast ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#include <bits/stdc++.h>
using namespace std;
#define sqr 340
#define mid (l+r)/2
#define pb push_back
#define ppb pop_back
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define ins insert
#define era erase
#define C continue
#define mem(dp,i) memset(dp,i,sizeof(dp))
#define mset multiset
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pi;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
const ll mod=1000000007;//998244353;
const ll inf=1e18*4;
const ld pai=acos(-1);
#include "dreaming.h"
int n,m,mx,id;
vpi v[100009];
vi ret;
int done[100009];
void fill(int node){
        done[node]=1;
        ret.pb(node);
        for(auto u:v[node]){
                if(done[u.fi])C;
                fill(u.fi);
        }
}
void MX(int node,int p,int crnt){
        if(crnt>mx)mx=crnt,id=node;
        for(auto u:v[node]){
                if(u.fi==p)C;
                MX(u.fi,node,crnt+u.se);
        }
}
pi go(){
        pi ans={1e9,1e9};
        for(auto u:ret){
                mx=-1;
                MX(u,u,0);
                ans=min(ans,{mx,u});
        }
        return ans;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
        n=N,m=M;
        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});
        }
        vpi all;
        for(int i=0;i<n;i++){
                if(done[i])C;
                ret.clear();
                fill(i);
                all.pb(go());
        }
        sort(all.begin(),all.end());
        reverse(all.begin(),all.end());
        for(int i=1;i<all.size();i++){
                int a=all[0].se,b=all[i].se,c=L;
                v[a].pb({b,c});
                v[b].pb({a,c});
        }
        mx=id=-1;
        MX(0,0,0);
        mx=-1;
        MX(id,id,0);
        return mx;
}

Compilation message

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:73: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 Execution timed out 1020 ms 11196 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1020 ms 11196 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1020 ms 11196 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 7688 KB Output is correct
2 Correct 47 ms 7796 KB Output is correct
3 Correct 47 ms 7720 KB Output is correct
4 Correct 47 ms 7712 KB Output is correct
5 Correct 46 ms 7716 KB Output is correct
6 Correct 53 ms 8688 KB Output is correct
7 Correct 54 ms 8128 KB Output is correct
8 Correct 49 ms 7888 KB Output is correct
9 Correct 43 ms 7604 KB Output is correct
10 Correct 47 ms 7928 KB Output is correct
11 Correct 4 ms 2680 KB Output is correct
12 Correct 28 ms 7788 KB Output is correct
13 Correct 27 ms 7788 KB Output is correct
14 Correct 30 ms 7788 KB Output is correct
15 Correct 29 ms 7784 KB Output is correct
16 Correct 45 ms 7784 KB Output is correct
17 Correct 32 ms 7784 KB Output is correct
18 Correct 29 ms 7800 KB Output is correct
19 Correct 31 ms 7788 KB Output is correct
20 Correct 5 ms 2680 KB Output is correct
21 Correct 5 ms 2680 KB Output is correct
22 Correct 5 ms 2808 KB Output is correct
23 Correct 29 ms 7756 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1020 ms 11196 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1020 ms 11196 KB Time limit exceeded
2 Halted 0 ms 0 KB -