oj.uz

Submission #1012431

# Submission time Handle Problem Language Result Execution time Memory
1012431 2024-07-02T07:12:49 Z amirhoseinfar1385 Dreaming (IOI13_dreaming) C++17
0 / 100
 1000 ms 16460 KB 
#include "dreaming.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10;
struct yal{
    int u,v,w;
    int getad(int fu){
        return (u^v^fu);
    }
}alle[maxn];
int n,m,l,mainres=0,vis[maxn];
vector<int>adj[maxn];
pair<int,int>mx[maxn];


pair<int,int>comp(pair<int,int>a,int b){
    if(b>a.first){
        a.first=b;
        if(a.first>a.second){
            swap(a.first,a.second);
        }
    }
    return a;
}

void dfsdown(int u,int par=-1){
    mx[u]=make_pair(0,0);
    for(auto x:adj[u]){
        int v=alle[x].getad(u);
        if(v==par){
            continue;
        }
        dfsdown(v,u);
        mx[u]=comp(mx[u],mx[v].second+alle[x].w);
    }
    return ;
}

void dfsup(int u,int par=-1,int l=-1){
    mx[u]=comp(mx[u],l);
    mainres=max(mainres,mx[u].first+mx[u].second);
    for(auto x:adj[u]){
        int v=alle[x].getad(u);
        if(v==par){
            continue;
        }
        int z=mx[u].second;
        if(mx[u].second==mx[v].second+alle[x].w){
            z=mx[u].first;
        }
        dfsup(v,u,z);
    }
}

int get(int u,int par=-1){
    int ret=u;
    for(auto x:adj[u]){
        int v=alle[x].getad(u);
        if(v==par){
            continue;
        }
        int r=get(v,u);
        if(mx[ret].second>mx[r].second){
            ret=r;
        }
    }
    return ret;
}

int calc(int u){
    dfsdown(u);
    dfsup(u);
    return get(u);
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    n=N;
    m=M;
    l=L;
    for(int i=0;i<m;i++){
        alle[i].u=A[i];
        alle[i].v=B[i];
        alle[i].w=T[i];
        adj[alle[i].u].push_back(i);
        adj[alle[i].v].push_back(i);
    }
    vector<int>alls;
    for(int i=1;i<=n;i++){
        if(vis[i]==0){
            alls.push_back(calc(i));
        }
    }
    sort(alls.rbegin(),alls.rend());
    if((int)alls.size()==2){
        mainres=max(mainres,alls[0]+alls[1]+l);
    }
    if((int)alls.size()>=3){
        mainres=max(mainres,alls[0]+alls[1]+l);
        mainres=max(mainres,alls[1]+alls[2]+2*l);
    }
    return mainres;
}

Subtask #1
0 / 14.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4696 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Incorrect 1 ms 4440 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

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

Subtask #4
0 / 18.0

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

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4696 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Incorrect 1 ms 4440 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

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