oj.uz

Submission #172475

# Submission time Handle Problem Language Result Execution time Memory
172475 2020-01-01T16:05:48 Z Lukoloz Dreaming (IOI13_dreaming) C++14
0 / 100
 75 ms 11516 KB 
#include "dreaming.h"
#include <bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define pb push_back
#define MAXN 100005
#define INF 999999999
using namespace std;
int ind,dpu[MAXN],dpd[MAXN],mx[MAXN][2],arr[MAXN],ans,ans1,per[MAXN];
int N,M,L,A[MAXN],B[MAXN],T[MAXN];
vector <pair<int,int> > g[MAXN];
bool fl[MAXN];
void dfs1(int i){
    fl[i]=1;
    for (int j=0; j<g[i].size(); j++){
        if (fl[g[i][j].ff]) continue;
        dfs1(g[i][j].ff);
        dpd[i]=max(dpd[i],dpd[g[i][j].ff]+g[i][j].ss);
    }
    fl[i]=0;
}
void dfs2(int i){
    fl[i]=1;
    arr[ind]=min(arr[ind],max(dpu[i],dpd[i]));

    // cout<<i<<" - "<<dpu[i]<<" "<<dpd[i]<<endl;

    for (int j=0; j<g[i].size(); j++){
        if (fl[g[i][j].ff]) continue;
        if (dpd[g[i][j].ff]+g[i][j].ss>mx[i][0]) mx[i][0]=dpd[g[i][j].ff]+g[i][j].ss;
        sort(mx[i],mx[i]+2);
    }

    // cout<<mx[0]<<" - "<<mx[1]<<endl;

    for (int j=0; j<g[i].size(); j++){
        if (fl[g[i][j].ff]) continue;
        if (dpd[g[i][j].ff]+g[i][j].ss==mx[i][1]) dpu[g[i][j].ff]=max(dpu[i],mx[i][0])+g[i][j].ss;
        else dpu[g[i][j].ff]=max(dpu[i],mx[i][1])+g[i][j].ss;  
    }

    ans1=max(ans1,max(mx[i][0],dpu[i])+mx[i][1]);
    
    for (int j=0; j<g[i].size(); j++){
        if (fl[g[i][j].ff]) continue;
        dfs2(g[i][j].ff); 
    }
}
int travelTime(int n,int m,int l,int a[],int b[],int t[]){
    for (int i=0; i<m; i++){
        g[a[i]].pb({b[i],t[i]});
        g[b[i]].pb({a[i],t[i]});
    }
    
    for(int i=0; i<n; i++){
        if (fl[i]) continue;
        arr[ind]=INF;
        dfs1(i); 
        dfs2(i);
        // cout<<"------------ arr - "<<arr[ind]<<" "<<i<<endl;
        // cout<<mx[i][1]+mx[i][0]<<endl;
        ind++;
    }
    // cout<<ans1<<endl;

    sort(arr,arr+ind);

    ans=max(arr[ind-3]+arr[ind-2]+2*l,arr[ind-1]+arr[ind-2]+l);

    return max(ans,ans1);
}
// int main() {
    // cin>>N>>M>>L;
    // for (int i=0; i<M; i++) cin>>A[i]>>B[i]>>T[i];
    // cout<<travelTime(N,M,L,A,B,T)<<endl;
// }
/*
12 8 2
0 8 4
8 2 2
2 7 4
5 11 3
5 1 7
1 3 1
1 9 5
10 6 3

*/

Compilation message

dreaming.cpp: In function 'void dfs1(int)':
dreaming.cpp:16:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j=0; j<g[i].size(); j++){
                   ~^~~~~~~~~~~~
dreaming.cpp: In function 'void dfs2(int)':
dreaming.cpp:29:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j=0; j<g[i].size(); j++){
                   ~^~~~~~~~~~~~
dreaming.cpp:37:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j=0; j<g[i].size(); j++){
                   ~^~~~~~~~~~~~
dreaming.cpp:45:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j=0; j<g[i].size(); j++){
                   ~^~~~~~~~~~~~

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 11128 KB Output is correct
2 Correct 68 ms 11516 KB Output is correct
3 Correct 45 ms 9592 KB Output is correct
4 Correct 13 ms 3964 KB Output is correct
5 Correct 11 ms 3576 KB Output is correct
6 Correct 20 ms 4696 KB Output is correct
7 Incorrect 4 ms 2680 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 11128 KB Output is correct
2 Correct 68 ms 11516 KB Output is correct
3 Correct 45 ms 9592 KB Output is correct
4 Correct 13 ms 3964 KB Output is correct
5 Correct 11 ms 3576 KB Output is correct
6 Correct 20 ms 4696 KB Output is correct
7 Incorrect 4 ms 2680 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 11128 KB Output is correct
2 Correct 68 ms 11516 KB Output is correct
3 Correct 45 ms 9592 KB Output is correct
4 Correct 13 ms 3964 KB Output is correct
5 Correct 11 ms 3576 KB Output is correct
6 Correct 20 ms 4696 KB Output is correct
7 Incorrect 4 ms 2680 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 7160 KB Output is correct
2 Correct 33 ms 7416 KB Output is correct
3 Correct 34 ms 7184 KB Output is correct
4 Correct 34 ms 7288 KB Output is correct
5 Correct 35 ms 7160 KB Output is correct
6 Correct 36 ms 7544 KB Output is correct
7 Correct 39 ms 7492 KB Output is correct
8 Correct 34 ms 7184 KB Output is correct
9 Correct 36 ms 6776 KB Output is correct
10 Correct 36 ms 7416 KB Output is correct
11 Correct 6 ms 2680 KB Output is correct
12 Correct 9 ms 4472 KB Output is correct
13 Correct 9 ms 4600 KB Output is correct
14 Correct 9 ms 4344 KB Output is correct
15 Correct 9 ms 4600 KB Output is correct
16 Correct 9 ms 4220 KB Output is correct
17 Correct 8 ms 3576 KB Output is correct
18 Correct 9 ms 4728 KB Output is correct
19 Correct 9 ms 4344 KB Output is correct
20 Incorrect 4 ms 2680 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 11128 KB Output is correct
2 Correct 68 ms 11516 KB Output is correct
3 Correct 45 ms 9592 KB Output is correct
4 Correct 13 ms 3964 KB Output is correct
5 Correct 11 ms 3576 KB Output is correct
6 Correct 20 ms 4696 KB Output is correct
7 Incorrect 4 ms 2680 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 11128 KB Output is correct
2 Correct 68 ms 11516 KB Output is correct
3 Correct 45 ms 9592 KB Output is correct
4 Correct 13 ms 3964 KB Output is correct
5 Correct 11 ms 3576 KB Output is correct
6 Correct 20 ms 4696 KB Output is correct
7 Incorrect 4 ms 2680 KB Output isn't correct
8 Halted 0 ms 0 KB -