oj.uz

Submission #394394

# Submission time Handle Problem Language Result Execution time Memory
394394 2021-04-26T13:48:19 Z teehandsome Dreaming (IOI13_dreaming) C++11
14 / 100
 61 ms 27460 KB 
#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

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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 10824 KB Output is correct
2 Correct 59 ms 10724 KB Output is correct
3 Correct 39 ms 8872 KB Output is correct
4 Correct 10 ms 5812 KB Output is correct
5 Correct 9 ms 5612 KB Output is correct
6 Correct 15 ms 6220 KB Output is correct
7 Correct 3 ms 4940 KB Output is correct
8 Correct 30 ms 7652 KB Output is correct
9 Correct 38 ms 8192 KB Output is correct
10 Correct 3 ms 4940 KB Output is correct
11 Correct 55 ms 9540 KB Output is correct
12 Correct 61 ms 10112 KB Output is correct
13 Correct 3 ms 5068 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 9932 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 10824 KB Output is correct
2 Correct 59 ms 10724 KB Output is correct
3 Correct 39 ms 8872 KB Output is correct
4 Correct 10 ms 5812 KB Output is correct
5 Correct 9 ms 5612 KB Output is correct
6 Correct 15 ms 6220 KB Output is correct
7 Correct 3 ms 4940 KB Output is correct
8 Correct 30 ms 7652 KB Output is correct
9 Correct 38 ms 8192 KB Output is correct
10 Correct 3 ms 4940 KB Output is correct
11 Correct 55 ms 9540 KB Output is correct
12 Correct 61 ms 10112 KB Output is correct
13 Correct 3 ms 5068 KB Output is correct
14 Runtime error 9 ms 9932 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 55 ms 27460 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 9932 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 10824 KB Output is correct
2 Correct 59 ms 10724 KB Output is correct
3 Correct 39 ms 8872 KB Output is correct
4 Correct 10 ms 5812 KB Output is correct
5 Correct 9 ms 5612 KB Output is correct
6 Correct 15 ms 6220 KB Output is correct
7 Correct 3 ms 4940 KB Output is correct
8 Correct 30 ms 7652 KB Output is correct
9 Correct 38 ms 8192 KB Output is correct
10 Correct 3 ms 4940 KB Output is correct
11 Correct 55 ms 9540 KB Output is correct
12 Correct 61 ms 10112 KB Output is correct
13 Correct 3 ms 5068 KB Output is correct
14 Runtime error 9 ms 9932 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -