oj.uz

Submission #444001

# Submission time Handle Problem Language Result Execution time Memory
444001 2021-07-12T20:44:52 Z Supersonic Dreaming (IOI13_dreaming) C++14
18 / 100
 54 ms 13508 KB 
#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
vector<pair<int,int>> g[100001];int c[100001];int cc=1;int ld[100001];int rd[100001];
int cf=-1,cd=-1;int u[100001];
void mc(int i){
    //cerr<<i<<endl;
    c[i]=cc;
    for(auto j:g[i])if(c[j.first]==0)mc(j.first);
}
void ffd(int i,int d){
    if(d>cd){cd=d;cf=i;}
    u[i]=1;
    for(auto j:g[i])if(!u[j.first])ffd(j.first,d+j.second);
    u[i]=0;
}
int ff(int i){
    cf=cd=-1;
    ffd(i,0);
    return cf;
}
void fl(int i,int d){
    //cerr<<"L "<<i<<' '<<d<<endl;
    ld[i]=d;
    for(auto j:g[i])if(ld[j.first]==-1)fl(j.first,d+j.second);
}
void fr(int i,int d){
    //cerr<<"R "<<i<<' '<<d<<endl;
    rd[i]=d;
    for(auto j:g[i])if(rd[j.first]==-1)fr(j.first,d+j.second);
}
int travelTime(int n, int m, int L, int A[], int B[], int T[]) {
    //cerr<<n<<' '<<m<<endl;
    //cerr<<"A"<<endl;
    for(int i=0;i<m;i++){g[A[i]].push_back({B[i],T[i]});g[B[i]].push_back({A[i],T[i]});}
    //cerr<<n<<' '<<m<<endl;
    for(int i=0;i<n;i++)if(!c[i]){mc(i);cc++;}
    cc--;//cerr<<cc<<endl;
    //for(int i=0;i<n;i++)cerr<<c[i]<<' ';cerr<<endl;
    int cr=1;
    for(int i=0;i<n;i++)ld[i]=rd[i]=-1;
    for(int i=0;i<n;i++){
        if(c[i]!=cr)continue;
        if(cr>cc)break;
        int l=ff(i);int r=ff(l);
        fl(l,0);fr(r,0);
        cr++;
    }
    vector<int> s={-100000000};for(int i=1;i<=cc;i++)s.push_back(1e9+1);
    for(int i=0;i<n;i++)s[c[i]]=min(s[c[i]],max(ld[i],rd[i]));
    sort(s.begin(),s.end());//for(int i=1;i<=cc;i++)cout<<s[i]<<' ';cout<<endl;
    if(cc==1)return s[1];
    return max(s[cc]+s[cc-1]+L,s[cc-1]+s[cc-2]+2*L);
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 54 ms 13508 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2636 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 54 ms 13508 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 7172 KB Output is correct
2 Correct 29 ms 7264 KB Output is correct
3 Correct 30 ms 7248 KB Output is correct
4 Correct 38 ms 7244 KB Output is correct
5 Correct 29 ms 7176 KB Output is correct
6 Correct 40 ms 7752 KB Output is correct
7 Correct 30 ms 7464 KB Output is correct
8 Correct 25 ms 7136 KB Output is correct
9 Correct 25 ms 7104 KB Output is correct
10 Correct 26 ms 7420 KB Output is correct
11 Correct 2 ms 2636 KB Output is correct
12 Correct 8 ms 4808 KB Output is correct
13 Correct 8 ms 4808 KB Output is correct
14 Correct 7 ms 4808 KB Output is correct
15 Correct 7 ms 4808 KB Output is correct
16 Correct 7 ms 4884 KB Output is correct
17 Correct 9 ms 4808 KB Output is correct
18 Correct 8 ms 4936 KB Output is correct
19 Correct 8 ms 4808 KB Output is correct
20 Correct 2 ms 2648 KB Output is correct
21 Correct 2 ms 2636 KB Output is correct
22 Correct 3 ms 2636 KB Output is correct
23 Correct 7 ms 4808 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2636 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 54 ms 13508 KB Output isn't correct
2 Halted 0 ms 0 KB -