Submission #1122633

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122633		Newtonabc	Dreaming (IOI13_dreaming)	C++20	0 / 100	1096 ms	10688 KiB

dreaming

#include "dreaming.h"
#include<bits/stdc++.h>
#define mp make_pair
using namespace std;
//n-m component
const int N=1e5+10;
bool vs[N];
int n,m,l,dist[N],cp,dista[N],distb[N];
queue<int> q;
vector<pair<int,int> > adj[N];
vector<int> com[N];
void bfs(int st,int *d){
    for(int i=0;i<n;i++) vs[i]=false;
    d[st]=0;
    vs[st]=true;
    q.push(st);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i=0;i<adj[u].size();i++){
            int v=adj[u][i].second;
            int w=adj[u][i].first;
            if(vs[v]) continue;
            d[v]=dist[u]+w;
            vs[v]=true;
            q.push(v);
        }
    }
}
int longnode(int st){
    int mx,mxval=-1;
    for(int i=0;i<n;i++) vs[i]=false;
    dist[st]=0;
    vs[st]=true;
    q.push(st);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i=0;i<adj[u].size();i++){
            int v=adj[u][i].second;
            int w=adj[u][i].first;
            if(vs[v]) continue;
            dist[v]=dist[u]+w;
            vs[v]=true;
            q.push(v);
        }
    }
    for(int i=0;i<n;i++){
        if(dist[i]>mxval){
            mxval=dist[i];
            mx=i;
        }
    }
    return mx;
}
void bfscom(int st){
    vs[st]=true;
    q.push(st);
    com[cp].push_back(st);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i=0;i<adj[u].size();i++){
            int v=adj[u][i].second;
            int w=adj[u][i].first;
            if(vs[v]) continue;
            com[cp].push_back(v);
            vs[v]=true;
            q.push(v);
        }
    }
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    n=N,m=M,l=L;
    int mx,mxval;
    for(int i=0;i<m;i++){
        adj[A[i]].push_back(mp(T[i],B[i]));
        adj[B[i]].push_back(mp(T[i],A[i]));
    }
    for(int i=0;i<n;i++){
        if(vs[i]) continue;
        cp++;
        bfscom(i);
    }
    vector<int> v;
    for(int i=1;i<=cp;i++){
        int u=com[i][0];
        int a=longnode(u);
        int b=longnode(a);
        bfs(a,dista);
        bfs(b,distb);
        int mnmax=INT_MAX;
        for(int j=0;j<com[i].size();j++){
            mnmax=min(max(dista[com[i][j]],distb[com[i][j]]),mnmax);
        }
        v.push_back(mnmax);
    }
    sort(v.begin(),v.end(),greater<int>());
    int ans=0;
    ans=max(ans,v[0]);
    if(v.size()>=2) ans=max(ans,v[0]+v[1]+l);
    if(v.size()>=3) ans=max(ans,v[1]+v[2]+2*l);
    return ans;
}

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