Submission #969263

#	Time	Username	Problem	Language	Result	Execution time	Memory
969263		anango	Dreaming (IOI13_dreaming)	C++17	100 / 100	116 ms	41576 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
int lau;
stack<int> S;
vector<vector<pair<int,int>>> adjlist;
vector<int> maxin;
vector<int> maxout;
vector<int> visited;
int n,m;


void dfs(int node) {
    S.push(node);
    visited[node] = 1;
    int maxmaxin=0;
    for (pair<int,int> nei:adjlist[node]) {
        if (visited[nei.first]) {
            continue;
        }
        dfs(nei.first);
        maxin[node] = max(maxin[node], maxin[nei.first]+nei.second); //maximum path from the node to any 
        //node in its subtree
    
    }
}
void dfs2(int node) {
    visited[node] = 1;
    int maxmaxin=0;
    vector<int> values;
    vector<pair<int,int>> children;
    int mout = maxout[node];
    for (pair<int,int> nei:adjlist[node]) {
        if (visited[nei.first]) {
            continue;
        }
        children.push_back(nei);
        values.push_back(nei.second+maxin[nei.first]);
    
    }
    int c=children.size();
    vector<int> prefmax(c+1,0);
    vector<int> suffmax(c+1,0);
    for (int i=0; i<c; i++) {
        prefmax[i+1] = max(prefmax[i], values[i]);
    }
    for (int i=c; i>=1; i--) {
        suffmax[i-1] = max(suffmax[i], values[i-1]);
    }
    


    for (int i=0; i<c; i++) {
        pair<int,int> nei=children[i];
        if (visited[nei.first]) {
            continue;
        }
        maxout[nei.first] = max(maxout[node],max(prefmax[i],suffmax[i+1]))+nei.second;
        dfs2(nei.first);
    }
}

signed travelTime(signed N, signed M, signed L, signed A[], signed B[], signed T[]) {
    n=N;
    m=M;
    lau=L;
    adjlist=vector<vector<pair<int,int>>>(N);
    visited=vector<int>(N,0);
    maxin=vector<int>(N,0);
    maxout=vector<int>(N,0);
    for (int i=0; i<M; i++) {
        adjlist[A[i]].push_back({B[i],T[i]});
        adjlist[B[i]].push_back({A[i],T[i]});
    }
    vector<vector<int>> conn;
    for (int i=0; i<n; i++) {
        if (!visited[i]) {
            dfs(i);
            vector<int> curcon;
            while (S.size()) {
                curcon.push_back(S.top());
                S.pop();
            }
            conn.push_back(curcon);
        }
    }
    visited=vector<int>(N,0);
    for (int i=0; i<n; i++) {
        if (!visited[i]) {
            dfs2(i);
        }
    }
    int c=conn.size();
    int INF=1000000000007;
    vector<int> weights(c,INF);
    int k=0;
    int tote=-1;
    for (auto i:conn) {
        for (auto j:i) {
            weights[k]=min(weights[k],max(maxin[j],maxout[j]));
            tote=max(tote,maxin[j]+maxout[j]);
        }
        k++;
    }
    sort(weights.begin(), weights.end());
    reverse(weights.begin(), weights.end());
    /*for (auto i:weights) {
        cout << i << " ";
    }
    cout << endl;*/
    if (weights.size()==1) {
        return max(tote,weights[0]);
    }
    else if (weights.size()==2) {
        return max(tote,weights[0]+weights[1]+L);
    }
    else { 
        return max(tote,max(weights[1]+weights[2]+2*L, weights[0]+weights[1]+L));
    }
    


}

Compilation message (stderr)

dreaming.cpp: In function 'void dfs(long long int)':
dreaming.cpp:17:9: warning: unused variable 'maxmaxin' [-Wunused-variable]
   17 |     int maxmaxin=0;
      |         ^~~~~~~~
dreaming.cpp: In function 'void dfs2(long long int)':
dreaming.cpp:30:9: warning: unused variable 'maxmaxin' [-Wunused-variable]
   30 |     int maxmaxin=0;
      |         ^~~~~~~~
dreaming.cpp:33:9: warning: unused variable 'mout' [-Wunused-variable]
   33 |     int mout = maxout[node];
      |         ^~~~

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