Submission #394394

#	Time	Username	Problem	Language	Result	Execution time	Memory
394394		teehandsome	Dreaming (IOI13_dreaming)	C++11	14 / 100	61 ms	27460 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define endl '\n'
#define INF 1e9+7
#define all(x) x.begin(),x.end()
using namespace std;
using namespace __gnu_pbds;
using ll=long long;
using pii=pair<int,int>;
using ppi=pair<int,pii>;
using oset=tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>;

template<typename T>
void _print(vector<T> x) {cerr<<"{"; for(auto e:x) cerr<<e<<","; cerr<<"}";}
void _print(pii x) {cerr<<"{"<<x.first<<","<<x.second<<"}";}
template<typename T>
void _print(T x) {cerr<<x;}

void dbg() {cerr<<endl;}
template<typename Head,typename... Tail>
void dbg(Head H,Tail... T) {
    _print(H);
    if(sizeof...(T)) cerr<<",";
    else cerr<<"\"]";
    dbg(T...);
}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:[\"",dbg(__VA_ARGS__)

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int mxn=1e5+10;
int n,m,l;
vector<pii> adj[mxn];
set<int> par_list;
int group_idx[mxn]; // which group node i belong to
vector<int> group[mxn];
int p[mxn];
vector<int> essen;
int ans;

int findp(int x) {
    while(p[x]!=x) p[x]=p[p[x]],x=p[x];
    return x;
}
void unionset(int u,int v) {
    int U=findp(u),V=findp(v);
    p[U]=V;
}
void solve(int root,int ii) {
    vector<int> dist(n,-1);
    queue<pii> q;
    q.push({root,0});
    int mx=0,idx=-1;
    while(!q.empty()) {
        int u=q.front().first;
        int d=q.front().second;
        q.pop();
        dist[u]=d;
        if(dist[u]>mx) {
            mx=dist[u]; idx=u;
        }
        for(auto vw:adj[u]) {
            int v=vw.first,w=vw.second;
            if(dist[v]==-1) {
                dist[v]=d+w;
                q.push({v,d+w});
            }
        }
    }
    int mx2=0,idx2=-1;
    queue<pii> q2;
    fill(all(dist),-1);
    q2.push({idx,0});
    while(!q2.empty()) {
        int u=q2.front().first;
        int d=q2.front().second;
        q2.pop();
        dist[u]=d;
        if(dist[u]>mx2) {
            mx2=dist[u],idx2=u;
        }
        for(auto vw:adj[u]) {
            int v=vw.first,w=vw.second;
            if(dist[v]==-1) {
                dist[v]=w+d;
                q2.push({v,w+d});
            }
        }
    }
    vector<int> dist2(n,-1);
    queue<pii> q3;
    q3.push({idx2,0});
    while(!q3.empty()) {
        int u=q3.front().first;
        int d=q3.front().second;
        q3.pop();
        dist2[u]=d;

        for(auto vw:adj[u]) {
            int v=vw.first,w=vw.second;
            if(dist2[v]==-1) {
                dist2[v]=w+d;
                q3.push({v,w+d});
            }
        }
    }
    int mn=INF;
    for(auto e:group[root]) {
        mn=min(mn,max(dist[e],dist2[e]));
    }
    ans=max(ans,mx2);
    essen.push_back(mn);
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    n=N,m=M,l=L;
    if(n==1) return 0;
    if(n==2) return l;
    for(int i=0;i<n;i++) p[i]=i;
    for(int i=0;i<m;i++) {
        int u=A[i],v=B[i],w=T[i];
        adj[u].push_back({v,w});
        adj[v].push_back({u,w});
        unionset(u,v);
    }
    for(int i=0;i<n;i++) {
        p[i]=findp(p[i]);
        group_idx[i]=p[i];
        group[p[i]].push_back(i);
        par_list.insert(p[i]);
    }
    int sz=par_list.size();
    int cnt=0;
    for(auto e:par_list) {
        solve(e,cnt++);
    }
    sort(all(essen),greater<int>());
    ans=max(ans,essen[0]+essen[1]+l);
    return ans;
}

Compilation message (stderr)

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:134:9: warning: unused variable 'sz' [-Wunused-variable]
  134 |     int sz=par_list.size();
      |         ^~

• Subtask 1: 14 / 14
• Subtask 2: 0 / 10
• Subtask 3: 0 / 23
• Subtask 4: 0 / 18
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23