oj.uz

Submission #468579

# Submission time Handle Problem Language Result Execution time Memory
468579 2021-08-28T20:12:48 Z Carmel_Ab1 Dreaming (IOI13_dreaming) C++17
0 / 100
 118 ms 32064 KB 
#include <bits/stdc++.h>
using namespace std;
#include "dreaming.h"
//#include "grader.cpp"

#define all(x) x.begin(),x.end()
#define umap unordered_map
#define pb push_back

typedef vector<int>vi;
typedef vector<vi> vvi;
typedef pair<int,int>pi;
typedef vector<pi> vpi;

vi par,mx;
umap<int,umap<int,int>>c;
int get(int x){return par[x]=(x==par[x]?x:get(par[x]));}
void unite(int u,int v,int L){
    u=get(u),v=get(v);
    if(u==v)return;
    if(mx[u]>mx[v])
        swap(u,v);
    mx[u]=max(mx[u],L+mx[v]);
    par[v]=u;
}

vi dijkstra(vvi g,int src){
    int n=g.size();
    vi d(n,1e9);
    vector<bool>vis(n);

    priority_queue<pi,vpi,greater<pi>>pq;
    pq.push({0,src});
    while(pq.size()){
        pi p=pq.top();
        pq.pop();

        src=p.second;
        int dst=p.first;
        if(vis[src])
            continue;
        vis[src]=1;
        d[src]=dst;
        for(int nbr:g[src])
            if(!vis[nbr])
                pq.push({dst+c[src][nbr],nbr});
    }
    return d;
}
int midpoint(vvi g){
    return 0;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    par.resize(N);
    mx.resize(N);

    vvi g(N);
    for(int i=0; i<N-2; i++){
        int u=A[i],v=B[i],w=T[i];
        g[u].pb(v);
        g[v].pb(u);

        c[u][v]=c[v][u]=w;
        unite(u,v,w);
    }
    for(int i=0; i<N-1; i++)
        unite(i,i+1,L);
    return mx[get(0)];
}

Subtask #1
0 / 14.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 23.0

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

Subtask #4
0 / 18.0

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

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

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