Submission #1122650

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122650		Newtonabc	Dreaming (IOI13_dreaming)	C++20	100 / 100	74 ms	11968 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];
int tmp;
void bfs(int st,int *d,int type){
    for(int i=0;i<com[type].size();i++) vs[com[type][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]=d[u]+w;
            vs[v]=true;
            q.push(v);
        }
    }
}
int longnode(int st,int type,int sp=1){
    int mx,mxval=-1;
    for(int i=0;i<com[type].size();i++) vs[com[type][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<com[type].size();i++){
        if(dist[com[type][i]]>mxval){
            mxval=dist[com[type][i]];
            mx=com[type][i];
        }
    }
    if(sp==2) tmp=mxval;
    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 ans=0;
    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++){
        if(com[i].size()==1){
            v.push_back(0);
            continue;
        }
        int u=com[i][0];
        int a=longnode(u,i);
        int b=longnode(a,i,2);
        ans=max(ans,tmp);
        bfs(a,dista,i);
        bfs(b,distb,i);
        int mnmax=INT_MAX;
        //cout<<u <<" " <<a <<" " <<b <<"\n";
        for(int j=0;j<com[i].size();j++){
            //cout<<com[i][j] <<" " <<dista[com[i][j]] <<" " <<distb[com[i][j]] <<"\n";
            mnmax=min(max(dista[com[i][j]],distb[com[i][j]]),mnmax);
        }
        //cout<<mnmax <<"\n\n";
        v.push_back(mnmax);
    }
    sort(v.begin(),v.end(),greater<int>());
    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;
}
/*int tmpa[N],tmpb[N],tmpt[N];
int main(){
    int n,m,l;
    cin>>n >>m >>l;
    for(int i=0;i<m;i++){
        cin>>tmpa[i] >>tmpb[i] >> tmpt[i];
    }
    cout<<travelTime(n,m,l,tmpa,tmpb,tmpt);
}*/

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