oj.uz

Submission #800635

# Submission time Handle Problem Language Result Execution time Memory
800635 2023-08-01T17:11:15 Z Boomyday Dreaming (IOI13_dreaming) C++17
18 / 100
 44 ms 13556 KB 
// My Header
#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;

using ll = long long;
using ld = long double;
using db = double;
using str = string; // yay python!

using ii = pair<int,int>;
using pl = pair<ll,ll>;
using pd = pair<db,db>;

using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<ll>;
using vd = vector<db>;
using vs = vector<str>;
using vii = vector<ii>;
using vpl = vector<pl>;
using vpd = vector<pd>;

#define tcT template<class T
#define tcTU tcT, class U

tcT> using V = vector<T>;
tcT, size_t SZ> using AR = array<T,SZ>;
tcT> using PR = pair<T,T>;

// pairs
#define mp make_pair
#define f first
#define s second

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

#define len(x) int((x).size())
#define bg(x) begin(x)
#define all(x) bg(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define sor(x) sort(all(x))
#define rsz resize
#define ins insert
#define ft front()
#define bk back()
#define pb push_back
#define eb emplace_back
#define pf push_front

const int MOD = 1e9+7; // 998244353;
const int MX = 2e5+5;
const ll INF = 1e18; // not too close to LLONG_MAX
const ld PI = acos((ld)-1);
const int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1}; // for every grid problem!!

vb vis1,vis2;
vi dist1,par,pdist;
vector<vii> adj;

int furthest=0; int far=0;




void far1(int nd){
    vis1[nd] = 1;

    for(auto&[cost, nei]:adj[nd]) if (!vis1[nei]) {
            dist1[nei] = dist1[nd] + cost;
            far1(nei);
        }
    if (dist1[nd] > furthest){
        furthest = dist1[nd];
        far = nd;
    }

}

void far2(int nd){


    vis2[nd] = 1;

    for(auto&[cost, nei]:adj[nd]) if (!vis2[nei]) {
            //
            //
            //


            par[nei] = nd;
            pdist[nei] = cost;
            dist1[nei] = dist1[nd] + cost;
            far2(nei);


        }


    if (dist1[nd] > furthest){

        furthest = dist1[nd];
        far = nd;
        //cout << "foo " << far << endl;
    }



}


int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
    adj.rsz(n);
    vis1.rsz(n);
    vis2.rsz(n);
    dist1.rsz(n);
    par.rsz(n);
    pdist.rsz(n);
    fill(all(vis1),0);
    fill(all(vis2),0);
    fill(all(dist1),0);
    fill(all(par),0);
    fill(all(pdist),0);
    F0R(i, m){
        adj[a[i]].pb({t[i],b[i]});
        adj[b[i]].pb({t[i],a[i]});
    }

    int greatestTravelTime = 0;
    vi radii;

    F0R(i, n){

        if (vis1[i]) continue;

        furthest = 0;
        far = i;
        dist1[i] = 0;
        far1(i);
        //cout << "foo" << endl;
        int xx = far;

        furthest = 0;
        far = xx;
        dist1[xx] = 0;
        //cout << "bar" << endl;
        far2(xx);
        //cout << "bar" << endl;
        int yy = far;
        //cout << i << " " << xx << " " << yy << endl;
        int dd = furthest;
        greatestTravelTime = max(greatestTravelTime,dd);
        vi dists;
        int cur = yy;
        while(cur != xx){
            dists.pb(pdist[cur]);
            cur = par[cur];
        }

        //trav(k, dists) cout << k << " "; cout << endl;
        int radius;
        int dsum = 0;

        if (dsum >= dd/2) radius = dsum;
        else trav(d, dists){
                dsum += d;
                if (dsum >= dd/2){ radius = dsum; break;}
            }
        reverse(all(dists));
        dsum = 0;
        if (dsum >= dd/2) radius = min(radius,dsum);
        else trav(d, dists){
                dsum += d;
                if (dsum >= dd/2){ radius = min(radius,dsum); break;}
            }
        radii.pb(radius);


    }










    //trav(i, radii) cout << i << " "; cout << endl;

    sort(all(radii),greater<int>());

    if (radii.size()>1){
        greatestTravelTime = max(greatestTravelTime,radii[0]+radii[1]+l);
    }
    if (radii.size()>2){
        greatestTravelTime = max(greatestTravelTime,radii[2]+radii[1]+2*l);
    }

    return greatestTravelTime;

}


/*
#include <stdio.h>
#include <stdlib.h>


#define fail(s, x...) do { \
		fprintf(stderr, s "\n", ## x); \
		exit(1); \
	} while(0)

#define MAX_N 100000

static int A[MAX_N];
static int B[MAX_N];
static int T[MAX_N];

int main() {



    int N, M, L, i;
    int res;

    FILE *f = fopen("dreaming.in", "r");
    if (!f)
        fail("Failed to open input file.");

    res = fscanf(f, "%d%d%d", &N, &M, &L);
    for (i = 0; i < M; i++)
        res = fscanf(f, "%d%d%d", &A[i], &B[i], &T[i]);
    fclose(f);

    int answer = travelTime(N, M, L, A, B, T);
    printf("%d\n", answer);

    return 0;
}*/

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 12376 KB Output is correct
2 Correct 31 ms 13556 KB Output is correct
3 Correct 21 ms 9072 KB Output is correct
4 Correct 6 ms 2220 KB Output is correct
5 Correct 6 ms 1492 KB Output is correct
6 Correct 8 ms 3228 KB Output is correct
7 Incorrect 0 ms 308 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 308 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 312 KB Output is correct
21 Incorrect 0 ms 308 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 12376 KB Output is correct
2 Correct 31 ms 13556 KB Output is correct
3 Correct 21 ms 9072 KB Output is correct
4 Correct 6 ms 2220 KB Output is correct
5 Correct 6 ms 1492 KB Output is correct
6 Correct 8 ms 3228 KB Output is correct
7 Incorrect 0 ms 308 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 15 ms 6232 KB Output is correct
2 Correct 21 ms 6760 KB Output is correct
3 Correct 15 ms 6652 KB Output is correct
4 Correct 16 ms 6720 KB Output is correct
5 Correct 16 ms 6716 KB Output is correct
6 Correct 16 ms 7356 KB Output is correct
7 Correct 16 ms 6992 KB Output is correct
8 Correct 15 ms 6616 KB Output is correct
9 Correct 15 ms 6584 KB Output is correct
10 Correct 17 ms 6840 KB Output is correct
11 Correct 1 ms 308 KB Output is correct
12 Correct 7 ms 4432 KB Output is correct
13 Correct 5 ms 4560 KB Output is correct
14 Correct 5 ms 4432 KB Output is correct
15 Correct 6 ms 4528 KB Output is correct
16 Correct 5 ms 4528 KB Output is correct
17 Correct 4 ms 4532 KB Output is correct
18 Correct 4 ms 4568 KB Output is correct
19 Correct 4 ms 4524 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 1 ms 436 KB Output is correct
23 Correct 4 ms 4432 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 308 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 312 KB Output is correct
21 Incorrect 0 ms 308 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 12376 KB Output is correct
2 Correct 31 ms 13556 KB Output is correct
3 Correct 21 ms 9072 KB Output is correct
4 Correct 6 ms 2220 KB Output is correct
5 Correct 6 ms 1492 KB Output is correct
6 Correct 8 ms 3228 KB Output is correct
7 Incorrect 0 ms 308 KB Output isn't correct
8 Halted 0 ms 0 KB -