oj.uz

Submission #625128

# Submission time Handle Problem Language Result Execution time Memory
625128 2022-08-09T12:53:27 Z SAAD Dreaming (IOI13_dreaming) C++17
0 / 100
 43 ms 13516 KB 
#define F first
#define S second
#define rep(i,a,b) for(int i=a;!(a==b&&i!=b)&&((i<=b&&b>=a)||(i>=b&&a>=b));i+=(a<=b?1:-1))
#define pb push_back
#define Fbitl __builtin_ffs
#define bit1 __builtin_popcount
#include <iostream>
#include <math.h>
#include <algorithm>
#include <string.h>
#include <vector>
#include <queue>
#include <map>
#include <unordered_map>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<string, string> pss;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vii;
typedef vector<ll> vl;
typedef vector<vl> vvl;
bool visa[(int)1e6];
#include "dreaming.h"
const int Ne = 1e5 + 5;
int mx, idmx;
bool th = false;
vii x[Ne];
vii res;
int R;
int mn = 1e9 , idmn = 1e9;
int dfs(int idx, int cst, int prnt) {
    int res = 0;
    visa[idx] = true;
    if (idx == R&&th) {
        return cst;
    }
    for (auto i : x[idx]) {
        if (i.first == prnt) continue;
        res += dfs(i.first, cst + i.second, idx);
    }
    if (res > 0) {
        int mex = max(cst,mx-cst);
        if (mex < mn) {
            mn = mex;
            idmn = idx;
        }
        return cst;
    }
    if (mx < cst) {
        mx = cst;
        idmx = idx;
    }
    if ( cst == 0 && !th) return idmx;
    if (th) {
        return 0;
    }
    return 0;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    for (int i = 0; i < M; i++) {
        x[A[i]].push_back({ B[i],T[i] });
        x[B[i]].push_back({ A[i],T[i] });
    }
    for (int i = 0; i < N; i++) {
        if (visa[i]) continue;
        th = false;
        mx = 0; idmx = 0;
        int a = dfs(i, 0, -1);
        mx = 0; idmx = 0;
        int b = dfs(a, 0, -1);
        
        if (x[i].empty()) {
            res.push_back({ 0,i });
            continue;
        }
        th = true;
        R = b;
        mn = 1e9, idmn = 1e9;
        dfs(a, 0, -1);
        res.push_back({mn,idmn});
    }
    sort(res.begin(), res.end());
    for (int i = 0; i < res.size() - 1; i++) {
        x[res[i].second].push_back({res[res.size()-1].second,L});
        //cout << res[i].second << " ";
    }
   
    mx = 0;
    for (int i = res.size()-1; i >= res.size() - 2 && i >= 0; i--,mx+=L) {
        mx += res[i].first;
    }
    mx -= L;
    return mx;
}

Compilation message

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:87: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]
   87 |     for (int i = 0; i < res.size() - 1; i++) {
      |                     ~~^~~~~~~~~~~~~~~~
dreaming.cpp:93:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |     for (int i = res.size()-1; i >= res.size() - 2 && i >= 0; i--,mx+=L) {
      |                                ~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 14.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 23.0

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

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 6940 KB Output is correct
2 Incorrect 23 ms 6888 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

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