oj.uz

Submission #1077069

# Submission time Handle Problem Language Result Execution time Memory
1077069 2024-08-26T22:18:21 Z MrPavlito Dreaming (IOI13_dreaming) C++17
32 / 100
 40 ms 14164 KB 
#include "dreaming.h"
#include <bits/stdc++.h>
//#define int long long
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define sc second
#define pii pair<int,int>

using namespace std;

const int MAXN = 1e5+5;
const int mod7 = 1e9+7;
const long long inf = 1e18;
int n;

bool visited[MAXN];
int parents[MAXN];
vector<vector<pii>> graf(MAXN);
vector<long long> dist;
long long mxdist;
long long rez = inf;
long long konacno= 0;

void dfs1(int nod, int p, long long d, int &kraj)
{
    parents[nod] = p;
    visited[nod] = 1;
    if(d>=mxdist)
    {
        kraj = nod;
        mxdist = d;
    }
    for(auto x: graf[nod])if(x.fi!=p)dfs1(x.fi, nod, d+x.sc, kraj);
}

void dfs2(int nod, int p, long long d)
{
    rez = min(rez, max(mxdist -d, d));
    int tr = rez;
    for(auto x: graf[nod])
    {
        if(x.fi == p)continue;
        int p1 = parents[x.fi];
        if(parents[x.fi] == nod)
        {
            dfs2(x.fi, nod, d+x.sc);
        }
    }

}

void solve(int i)
{
    int nod1 = i;
    mxdist = 0;
    dfs1(i,i,0, nod1);
    int nod2 = i;
    mxdist = 0;
    dfs1(nod1, nod1, 0, nod2);
    rez = inf;
    dfs2(nod1, nod1, 0);
    konacno = max(konacno, mxdist);
    dist.pb(rez);
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    n = N;
    for(int i=0; i<M; i++)
    {
        graf[A[i]].pb(mp(B[i], T[i]));
        graf[B[i]].pb(mp(A[i], T[i]));
    }
    for(int i=0; i<n; i++)if(!visited[i])solve(i);
    sort(all(dist));
    reverse(all(dist));
    //for(auto x: dist)cout << x<< " ";cout << endl;
    if(M == n-1)return konacno;
    konacno = max(konacno,dist[0]+dist[1]+L);
    for(int i=2; i<(int)dist.size(); i++) konacno = max({konacno,dist[1]+dist[i]+2*L, dist[0]+dist[i]+L});
    return konacno;
}

Compilation message

dreaming.cpp: In function 'void dfs2(int, int, long long int)':
dreaming.cpp:45:13: warning: unused variable 'p1' [-Wunused-variable]
   45 |         int p1 = parents[x.fi];
      |             ^~
dreaming.cpp:41:9: warning: unused variable 'tr' [-Wunused-variable]
   41 |     int tr = rez;
      |         ^~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 14164 KB Output is correct
2 Correct 34 ms 13904 KB Output is correct
3 Correct 21 ms 10332 KB Output is correct
4 Correct 5 ms 4444 KB Output is correct
5 Correct 5 ms 3676 KB Output is correct
6 Correct 9 ms 5320 KB Output is correct
7 Correct 1 ms 2648 KB Output is correct
8 Correct 21 ms 6732 KB Output is correct
9 Correct 23 ms 8312 KB Output is correct
10 Correct 1 ms 2652 KB Output is correct
11 Correct 31 ms 10232 KB Output is correct
12 Correct 35 ms 11856 KB Output is correct
13 Correct 1 ms 2904 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 14164 KB Output is correct
2 Correct 34 ms 13904 KB Output is correct
3 Correct 21 ms 10332 KB Output is correct
4 Correct 5 ms 4444 KB Output is correct
5 Correct 5 ms 3676 KB Output is correct
6 Correct 9 ms 5320 KB Output is correct
7 Correct 1 ms 2648 KB Output is correct
8 Correct 21 ms 6732 KB Output is correct
9 Correct 23 ms 8312 KB Output is correct
10 Correct 1 ms 2652 KB Output is correct
11 Correct 31 ms 10232 KB Output is correct
12 Correct 35 ms 11856 KB Output is correct
13 Correct 1 ms 2904 KB Output is correct
14 Correct 1 ms 2652 KB Output is correct
15 Correct 1 ms 2776 KB Output is correct
16 Incorrect 1 ms 2652 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 6624 KB Output is correct
2 Correct 15 ms 6656 KB Output is correct
3 Correct 16 ms 6612 KB Output is correct
4 Correct 14 ms 6620 KB Output is correct
5 Correct 17 ms 6616 KB Output is correct
6 Correct 17 ms 7132 KB Output is correct
7 Correct 17 ms 6688 KB Output is correct
8 Correct 16 ms 6548 KB Output is correct
9 Correct 16 ms 6356 KB Output is correct
10 Correct 14 ms 6616 KB Output is correct
11 Correct 2 ms 2652 KB Output is correct
12 Correct 6 ms 4308 KB Output is correct
13 Correct 5 ms 4472 KB Output is correct
14 Correct 5 ms 4308 KB Output is correct
15 Correct 6 ms 4308 KB Output is correct
16 Correct 5 ms 4308 KB Output is correct
17 Correct 5 ms 4308 KB Output is correct
18 Correct 5 ms 4308 KB Output is correct
19 Correct 5 ms 4308 KB Output is correct
20 Correct 1 ms 2652 KB Output is correct
21 Correct 1 ms 2652 KB Output is correct
22 Correct 1 ms 2648 KB Output is correct
23 Correct 6 ms 4304 KB Output is correct

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 14164 KB Output is correct
2 Correct 34 ms 13904 KB Output is correct
3 Correct 21 ms 10332 KB Output is correct
4 Correct 5 ms 4444 KB Output is correct
5 Correct 5 ms 3676 KB Output is correct
6 Correct 9 ms 5320 KB Output is correct
7 Correct 1 ms 2648 KB Output is correct
8 Correct 21 ms 6732 KB Output is correct
9 Correct 23 ms 8312 KB Output is correct
10 Correct 1 ms 2652 KB Output is correct
11 Correct 31 ms 10232 KB Output is correct
12 Correct 35 ms 11856 KB Output is correct
13 Correct 1 ms 2904 KB Output is correct
14 Correct 1 ms 2652 KB Output is correct
15 Correct 1 ms 2776 KB Output is correct
16 Incorrect 1 ms 2652 KB Output isn't correct
17 Halted 0 ms 0 KB -