제출 #394355

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
394355		teehandsome	꿈 (IOI13_dreaming)	C++11	0 / 100	64 ms	11204 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;
int p[mxn];
vector<pii> adj[mxn];
vector<int> root;
vector<int> farth[2];
int dist[2][2][mxn];

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;
}

int dep[mxn];

void solve(int u,int ii) {
    memset(dep,-1,sizeof(dep));
    queue<pii> q;
    q.push({u,0});
    int mx=0,idx=-1;
    while(!q.empty()) {
        pii cur=q.front(); q.pop();
        int u=cur.first,d=cur.second;
        dep[u]=d;
        if(dep[u]>mx) {
            mx=dep[u]; idx=u;
        }
        for(auto vw:adj[u]) {
            if(dep[vw.first]==-1) {
                dep[vw.first]=d+vw.second;
                q.push({vw.first,dep[vw.first]});
            }
        }
    }
    farth[ii].push_back(idx);
    int mx2=0,idx2=-1;
    memset(dep,-1,sizeof(dep));
    queue<pii> q2;
    q2.push({idx,0});
    while(!q2.empty()) {
        pii cur=q2.front(); q2.pop();
        int u=cur.first,d=cur.second;
        dep[u]=d;
        if(dep[u]>mx2) {
            mx2=dep[u];
            idx2=u;
        }
        for(auto vw:adj[u]) {
            int v=vw.first,w=vw.second;
            if(dep[v]==-1) {
                dep[v]=d+w;
                q2.push({v,dep[v]});
            }
        }
    }
    farth[ii].push_back(idx2);

}
void finddist(int ii,int jj) {
    memset(dist[ii][jj],-1,sizeof(dist[ii][jj]));
    queue<pii> q;
    q.push({farth[ii][jj],0});
    while(!q.empty()) {
        pii cur=q.front(); q.pop();
        int u=cur.first,d=cur.second;
        dist[ii][jj][u]=d;
        for(auto vw:adj[u]) {
            int v=vw.first,w=vw.second;
            if(dist[ii][jj][v]==-1) {
                dist[ii][jj][v]=d+w;
                q.push({v,d+w});
            }
        }
    }
}
vector<int> group[2];

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<n;i++) p[i]=i;
    for(int i=0;i<m;i++) {
        unionset(A[i],B[i]);
        adj[A[i]].push_back({B[i],T[i]});
        adj[B[i]].push_back({A[i],T[i]});
    }
    for(int i=0;i<n;i++) {
        p[i]=findp(p[i]);
        root.push_back(p[i]);
    }
    sort(all(root));
    root.erase(unique(all(root)),root.end());
    assert(root.size()>1);

    for(int i=0;i<2;i++) {
        solve(root[i],i);
//        debug(farth[i]);
    }
    for(int i=0;i<2;i++) {
        for(int j=0;j<2;j++) {
            finddist(i,j);
        }
    }
    for(int i=0;i<n;i++) {
        if(p[i]==root[0]) group[0].push_back(i);
        else group[1].push_back(i);
    }
    int mn=INF;
    for(auto u:group[0]) {
        mn=min(mn,max(dist[0][0][u],dist[0][1][u]));
    }
    int mn2=INF;
    for(auto u:group[1]) {
        mn2=min(mn2,max(dist[1][0][u],dist[1][1][u]));
    }
    return mn+mn2+l;
}

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