oj.uz

Submission #575666

# Submission time Handle Problem Language Result Execution time Memory
575666 2022-06-11T07:36:27 Z enerelt14 Dreaming (IOI13_dreaming) C++17
18 / 100
 49 ms 15156 KB 
#include "dreaming.h"
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
using namespace std;
//int N, M, L, A[100005], B[100005], T[100005];
int p[100005], d[100005], ans=0;
int find(int s){
    if (s==p[s])return s;
    return p[s]=find(p[s]);
}
void Union_find(int x, int y){
    int z=find(x), t=find(y);
    p[max(z, t)]=min(z, t);
}
vector<pair<int, int> >adj[100005];
vector<int>x[100005];
vector<int>y;
int mx_d[100005]={0}, sec[100005]={0};
bool is[100005]={0};
void dfs(int u, int par){
    p[u]=par;
    for (int i=0;i<adj[u].size();i++){
        int v=adj[u][i].ff;
        if (v==par)continue;
        dfs(v, u);
        if (mx_d[u]<mx_d[v]+adj[u][i].ss){
            mx_d[u]=mx_d[v]+adj[u][i].ss;
            is[u]=0;
            continue;
        }
        if (mx_d[u]==mx_d[v]+adj[u][i].ss){
            is[u]=1;
        }
    }
    if (is[u])sec[u]=mx_d[u];
    for (int i=0;i<adj[u].size();i++){
        int v=adj[u][i].ff;
        if (v!=par && mx_d[u]!=mx_d[v]+adj[u][i].ss)sec[u]=max(sec[u], mx_d[v]+adj[u][i].ss);
    }
    ans=max(ans, mx_d[u]+sec[u]);
}
void solve(int s, int u, int dis){
    d[s]=min(d[s], max(dis, mx_d[u]));
    for (int i=0;i<adj[u].size();i++){
        int v=adj[u][i].ff;
        if (v==p[u])continue;
        if (mx_d[v]+adj[u][i].ss==mx_d[u])solve(s, v, max(dis, sec[u])+adj[u][i].ss);
        else solve(s, v, max(dis, mx_d[u])+adj[u][i].ss);
    }
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    memset(mx_d, 0, sizeof(mx_d));
    if (N==1)return 0;
    if (N==2){
        if (M==1)return T[0];
        else return L;
    }
    for (int i=0;i<N;i++)p[i]=i;
    for (int i=0;i<M;i++){
        Union_find(A[i], B[i]);
        adj[A[i]].pb(mp(B[i], T[i]));
        adj[B[i]].pb(mp(A[i], T[i]));
    }
    for (int i=0;i<N;i++){
        x[find(i)].pb(i);
    }
    for (int i=0;i<N;i++){
        if (x[i].empty())continue;
        y=x[i];
        dfs(y[0], y[0]);
        d[i]=mx_d[y[0]];
        for (int j=0;j<adj[y[0]].size();j++){
            if (mx_d[adj[y[0]][j].ff]+adj[y[0]][j].ss==mx_d[y[0]]){
                solve(i, adj[y[0]][j].ff, sec[y[0]]+adj[y[0]][j].ss);
            }
            else solve(i, adj[y[0]][j].ff, mx_d[y[0]]+adj[y[0]][j].ss);
        }
    }
    sort(d, d+N);
    ans=max(ans, max(d[N-1]+d[N-2]+L, d[N-2]+d[N-3]+2*L));
    return ans;
}

Compilation message

dreaming.cpp: In function 'void dfs(int, int)':
dreaming.cpp:25:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     for (int i=0;i<adj[u].size();i++){
      |                  ~^~~~~~~~~~~~~~
dreaming.cpp:39:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     for (int i=0;i<adj[u].size();i++){
      |                  ~^~~~~~~~~~~~~~
dreaming.cpp: In function 'void solve(int, int, int)':
dreaming.cpp:47:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     for (int i=0;i<adj[u].size();i++){
      |                  ~^~~~~~~~~~~~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:75:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |         for (int j=0;j<adj[y[0]].size();j++){
      |                      ~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 14908 KB Output is correct
2 Correct 49 ms 15156 KB Output is correct
3 Correct 34 ms 13532 KB Output is correct
4 Correct 8 ms 6900 KB Output is correct
5 Correct 8 ms 6356 KB Output is correct
6 Correct 16 ms 7692 KB Output is correct
7 Incorrect 3 ms 5392 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5332 KB Output is correct
2 Correct 3 ms 5332 KB Output is correct
3 Incorrect 3 ms 5460 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 14908 KB Output is correct
2 Correct 49 ms 15156 KB Output is correct
3 Correct 34 ms 13532 KB Output is correct
4 Correct 8 ms 6900 KB Output is correct
5 Correct 8 ms 6356 KB Output is correct
6 Correct 16 ms 7692 KB Output is correct
7 Incorrect 3 ms 5392 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 10392 KB Output is correct
2 Correct 34 ms 10836 KB Output is correct
3 Correct 38 ms 10728 KB Output is correct
4 Correct 34 ms 10844 KB Output is correct
5 Correct 31 ms 10784 KB Output is correct
6 Correct 33 ms 11116 KB Output is correct
7 Correct 35 ms 11072 KB Output is correct
8 Correct 35 ms 10700 KB Output is correct
9 Correct 30 ms 10692 KB Output is correct
10 Correct 33 ms 10960 KB Output is correct
11 Correct 3 ms 5332 KB Output is correct
12 Correct 11 ms 9428 KB Output is correct
13 Correct 11 ms 9428 KB Output is correct
14 Correct 11 ms 9428 KB Output is correct
15 Correct 11 ms 9372 KB Output is correct
16 Correct 11 ms 9428 KB Output is correct
17 Correct 10 ms 9384 KB Output is correct
18 Correct 11 ms 9376 KB Output is correct
19 Correct 10 ms 9360 KB Output is correct
20 Correct 3 ms 5332 KB Output is correct
21 Correct 3 ms 5396 KB Output is correct
22 Correct 3 ms 5520 KB Output is correct
23 Correct 12 ms 9412 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5332 KB Output is correct
2 Correct 3 ms 5332 KB Output is correct
3 Incorrect 3 ms 5460 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 14908 KB Output is correct
2 Correct 49 ms 15156 KB Output is correct
3 Correct 34 ms 13532 KB Output is correct
4 Correct 8 ms 6900 KB Output is correct
5 Correct 8 ms 6356 KB Output is correct
6 Correct 16 ms 7692 KB Output is correct
7 Incorrect 3 ms 5392 KB Output isn't correct
8 Halted 0 ms 0 KB -