oj.uz

Submission #394370

# Submission time Handle Problem Language Result Execution time Memory
394370 2021-04-26T12:54:31 Z teehandsome Dreaming (IOI13_dreaming) C++11
14 / 100
 72 ms 10004 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;
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 ans;
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]});
            }
        }
    }
    ans=max(ans,mx);
    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]});
            }
        }
    }
    ans=max(ans,mx2);
    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 max(ans,mn+mn2+l);
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 10004 KB Output is correct
2 Correct 68 ms 9920 KB Output is correct
3 Correct 43 ms 7948 KB Output is correct
4 Correct 11 ms 5444 KB Output is correct
5 Correct 10 ms 5176 KB Output is correct
6 Correct 17 ms 5828 KB Output is correct
7 Correct 3 ms 4556 KB Output is correct
8 Correct 33 ms 6968 KB Output is correct
9 Correct 42 ms 7492 KB Output is correct
10 Correct 3 ms 4556 KB Output is correct
11 Correct 60 ms 8512 KB Output is correct
12 Correct 72 ms 9432 KB Output is correct
13 Correct 3 ms 4556 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4556 KB Output is correct
2 Correct 3 ms 4556 KB Output is correct
3 Correct 3 ms 4556 KB Output is correct
4 Correct 3 ms 4556 KB Output is correct
5 Correct 3 ms 4556 KB Output is correct
6 Correct 3 ms 4556 KB Output is correct
7 Correct 3 ms 4552 KB Output is correct
8 Correct 3 ms 4556 KB Output is correct
9 Correct 3 ms 4556 KB Output is correct
10 Correct 3 ms 4556 KB Output is correct
11 Correct 3 ms 4556 KB Output is correct
12 Correct 3 ms 4556 KB Output is correct
13 Correct 3 ms 4556 KB Output is correct
14 Correct 3 ms 4556 KB Output is correct
15 Incorrect 3 ms 4556 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 10004 KB Output is correct
2 Correct 68 ms 9920 KB Output is correct
3 Correct 43 ms 7948 KB Output is correct
4 Correct 11 ms 5444 KB Output is correct
5 Correct 10 ms 5176 KB Output is correct
6 Correct 17 ms 5828 KB Output is correct
7 Correct 3 ms 4556 KB Output is correct
8 Correct 33 ms 6968 KB Output is correct
9 Correct 42 ms 7492 KB Output is correct
10 Correct 3 ms 4556 KB Output is correct
11 Correct 60 ms 8512 KB Output is correct
12 Correct 72 ms 9432 KB Output is correct
13 Correct 3 ms 4556 KB Output is correct
14 Correct 3 ms 4556 KB Output is correct
15 Correct 3 ms 4556 KB Output is correct
16 Correct 3 ms 4556 KB Output is correct
17 Correct 3 ms 4556 KB Output is correct
18 Correct 3 ms 4556 KB Output is correct
19 Correct 3 ms 4556 KB Output is correct
20 Correct 3 ms 4552 KB Output is correct
21 Correct 3 ms 4556 KB Output is correct
22 Correct 3 ms 4556 KB Output is correct
23 Correct 3 ms 4556 KB Output is correct
24 Correct 3 ms 4556 KB Output is correct
25 Correct 3 ms 4556 KB Output is correct
26 Correct 3 ms 4556 KB Output is correct
27 Correct 3 ms 4556 KB Output is correct
28 Incorrect 3 ms 4556 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 8396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4556 KB Output is correct
2 Correct 3 ms 4556 KB Output is correct
3 Correct 3 ms 4556 KB Output is correct
4 Correct 3 ms 4556 KB Output is correct
5 Correct 3 ms 4556 KB Output is correct
6 Correct 3 ms 4556 KB Output is correct
7 Correct 3 ms 4552 KB Output is correct
8 Correct 3 ms 4556 KB Output is correct
9 Correct 3 ms 4556 KB Output is correct
10 Correct 3 ms 4556 KB Output is correct
11 Correct 3 ms 4556 KB Output is correct
12 Correct 3 ms 4556 KB Output is correct
13 Correct 3 ms 4556 KB Output is correct
14 Correct 3 ms 4556 KB Output is correct
15 Incorrect 3 ms 4556 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 10004 KB Output is correct
2 Correct 68 ms 9920 KB Output is correct
3 Correct 43 ms 7948 KB Output is correct
4 Correct 11 ms 5444 KB Output is correct
5 Correct 10 ms 5176 KB Output is correct
6 Correct 17 ms 5828 KB Output is correct
7 Correct 3 ms 4556 KB Output is correct
8 Correct 33 ms 6968 KB Output is correct
9 Correct 42 ms 7492 KB Output is correct
10 Correct 3 ms 4556 KB Output is correct
11 Correct 60 ms 8512 KB Output is correct
12 Correct 72 ms 9432 KB Output is correct
13 Correct 3 ms 4556 KB Output is correct
14 Correct 3 ms 4556 KB Output is correct
15 Correct 3 ms 4556 KB Output is correct
16 Correct 3 ms 4556 KB Output is correct
17 Correct 3 ms 4556 KB Output is correct
18 Correct 3 ms 4556 KB Output is correct
19 Correct 3 ms 4556 KB Output is correct
20 Correct 3 ms 4552 KB Output is correct
21 Correct 3 ms 4556 KB Output is correct
22 Correct 3 ms 4556 KB Output is correct
23 Correct 3 ms 4556 KB Output is correct
24 Correct 3 ms 4556 KB Output is correct
25 Correct 3 ms 4556 KB Output is correct
26 Correct 3 ms 4556 KB Output is correct
27 Correct 3 ms 4556 KB Output is correct
28 Incorrect 3 ms 4556 KB Output isn't correct
29 Halted 0 ms 0 KB -