oj.uz

Submission #669383

# Submission time Handle Problem Language Result Execution time Memory
669383 2022-12-06T10:40:54 Z Bogdan1110 Dreaming (IOI13_dreaming) C++14
18 / 100
 62 ms 57288 KB 
#include <bits/stdc++.h>
#include "dreaming.h"
#define FAST {ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);}
#define FILES {freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);}
#define ll long long
#define ull unsigned long long
#define pqueue priority_queue
#define pb push_back
#define fi first
#define se second
#define ld long double
#define pii pair<int,int>
#define pll pair<long long,long long>
#define all(a) (a).begin(), (a).end()
#define mp make_pair 
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
 
#define ordered_set tree<pll, null_type,less<pll>, rb_tree_tag,tree_order_statistics_node_update>
// order_of_key -> # less than k
// find_by_order -> k-th element
// pq max element
 
const double eps = 0.00000001;
const int NMAX = 2000010;
const ll inf = LLONG_MAX/3;
const ll modi = 998244353;
 
int D, maks, mx;
vector<pii>al[NMAX];
int visited[NMAX], vv[NMAX];
int maksd,poc;
 
vector<int>vis,nes;
set<int>vektor;
 
void izr() {
    for (auto u : nes) {
        maks = min(maks, max(u,D-u));
    }
}
 
void dfs1(int node, int dist = 0) {
    if (visited[node]) {
        return;
    }
    vv[node] = 1;
    vis.pb(node);
    visited[node] =1;
    if ( dist > maksd ) {
        maksd = dist;
        poc = node;
    }
    for (auto u : al[node] ) {
        dfs1(u.fi, u.se + dist);
    }
}
 
void dfs2(int node, int dist = 0) {
    if (visited[node]||maks!= INT_MAX) {
        return;
    }
    vis.pb(node);
    visited[node] =1;
    nes.pb(dist);
    if ( dist == maksd ) {
        izr();
        return;
    }
    if ( dist > maksd ) {
        maksd = dist;
        poc = node;
    }
    for (auto u : al[node] ) {
        dfs2(u.fi, u.se + dist);
    }
    nes.erase(nes.end()-1);
}
 
void clrvis() {
    for (auto u : vis) {
        visited[u] = 0;
    }
    vis.clear();
}
 
int travelTime(int n,int m,int l,int A[],int B[],int T[]) {
    for (int i = 0 ; i < m; i++) {
        al[A[i]].pb({B[i],T[i]});
        al[B[i]].pb({A[i],T[i]});
    }
    vector<int>r;
    for (int i = 0 ; i < n ; i++ ) {
        if (!vv[i]) {
            maksd = -1;
            dfs1(i);
            clrvis();
 
            
            maksd = -1;
            dfs1(poc);
            clrvis();
 
            maks = INT_MAX;
            D = maksd;
 
            dfs2(poc);
            clrvis();
            nes.clear();
            r.pb(maks);
        }
    }
 
    //for (auto u : r) cout << u << ' ';
    
 
    sort(all(r));
    int res = r[r.size()-1];
  	if ( r.size() == 1 ) {
      	return res;
    }
  	if ( r.size() == 2 ) {
      	return res + r[0] + l;
    }
  
  	res = max(res, res + r[r.size()-2] + l);
  	res = max(res , r[r.size()-2] + l + r[r.size()-3] + l);
  	
    return res;
}

Subtask #1
0 / 14.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 23.0

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

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 50704 KB Output is correct
2 Correct 41 ms 50636 KB Output is correct
3 Correct 45 ms 51076 KB Output is correct
4 Correct 47 ms 51244 KB Output is correct
5 Correct 45 ms 51072 KB Output is correct
6 Correct 44 ms 51624 KB Output is correct
7 Correct 43 ms 51408 KB Output is correct
8 Correct 42 ms 51040 KB Output is correct
9 Correct 43 ms 51020 KB Output is correct
10 Correct 47 ms 51200 KB Output is correct
11 Correct 23 ms 47272 KB Output is correct
12 Correct 28 ms 48724 KB Output is correct
13 Correct 29 ms 48680 KB Output is correct
14 Correct 29 ms 48648 KB Output is correct
15 Correct 31 ms 48668 KB Output is correct
16 Correct 29 ms 48720 KB Output is correct
17 Correct 30 ms 48584 KB Output is correct
18 Correct 28 ms 48720 KB Output is correct
19 Correct 28 ms 48720 KB Output is correct
20 Correct 23 ms 47188 KB Output is correct
21 Correct 23 ms 47284 KB Output is correct
22 Correct 23 ms 47316 KB Output is correct
23 Correct 28 ms 48612 KB Output is correct

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

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