Submission #468579

#	Time	Username	Problem	Language	Result	Execution time	Memory
468579		Carmel_Ab1	Dreaming (IOI13_dreaming)	C++17	0 / 100	118 ms	32064 KiB

dreaming

#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
• Subtask 2: 0 / 10
• Subtask 3: 0 / 23
• Subtask 4: 0 / 18
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23