oj.uz

Submission #962172

# Submission time Handle Problem Language Result Execution time Memory
962172 2024-04-13T08:23:02 Z stev2005 Dreaming (IOI13_dreaming) C++17
0 / 100
 1000 ms 9564 KB 
#include "dreaming.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn = (1<<17), inf = (1<<30);
int n, m, lprice;

struct edge{
    int ver, cost;
    edge(){
        ver = -1;
        cost = 0;
    }
    edge(int _ver, int _cost){
        ver = _ver;
        cost = _cost;
    }
    bool operator<(const edge &other) const{
        return cost > other.cost;
    }
};

struct diamgr{
    int s, f;
    int cost, sum1, sum2;
    diamgr(){
        /*mid =*/ s = f = -1;
        cost = sum1 = sum2 = -1;
    }
    diamgr(int _s, int _f, int _cost, int _sum1, int _sum2){
        s = _s;
        f = _f;
        //mid = _mid;
        cost = _cost;
        sum1 = _sum1;
        sum2 = _sum2;
    }
};

vector <edge> v[maxn];
bool used[maxn];
bool checkver[maxn];
int parsum[maxn], parsum1[maxn], parsum2[maxn];

int anscost;
int d[maxn];
int par[maxn], costpar[maxn];


inline void init_vectors(int *a, int *b, int *t){
    for (int i = 0; i < m; ++i){
        v[a[i]].push_back(edge(b[i], t[i]));
        v[b[i]].push_back(edge(b[i], t[i]));
        //cerr << a[i] << " " << b[i] << " " << t[i] << endl;
    }
}

int Dijkstra(int beg){
    memset(used, 0, sizeof(used));
    memset(par, -1, sizeof(par));
    used[beg] = 1;
    checkver[beg] = 1;
    for (int i = 0; i < n; ++i)
        d[i] = inf;
    d[beg] = 0;
    costpar[beg] = 0;
    par[beg] = -1;
    priority_queue<edge> q;
    q.push(edge(beg, 0));
    int lastpopped = -1;
    while (!q.empty()){
        edge cur = q.top();
        q.pop();
        lastpopped = cur.ver;
        if (cur.cost <= d[cur.ver]){
            used[cur.ver] = 1;
            checkver[cur.ver] = 1;
            for (int i = 0; i < (int)v[cur.ver].size(); ++i){
                edge nb = v[cur.ver][i];
                if (cur.cost + nb.cost < d[nb.ver]){
                    par[nb.ver] = cur.ver;
                    costpar[nb.ver] = nb.cost;
                    d[nb.ver] = cur.cost + nb.cost;
                    nb.cost = d[nb.ver];
                    q.push(nb);
                }
            }
        }
    }
    return lastpopped;
}

int init_parsums(int s, int f, int *parsum){
    int cur = f, prev = -1;
    int cnt = 1;
    while (cur != s){
        parsum[cnt] = parsum[cnt - 1] + costpar[cur];
        cur = par[cur];
        cnt++;
    }
    return cnt;
}

pair<int, int> find_mindif(int n, int *parsum){
    if (n == 1) return {0, 0};
    if (n == 2) return {0, parsum[1]};
    int sum1 = -(1<<30) + 10, sum2 = (1<<30) - 10;
    for (int i = 0; i < n; ++i){
        int cursum1 = parsum[i];
        int cursum2 = parsum[n - 1] - parsum[i];
        if (abs(cursum2 - cursum1) < abs(sum2 - sum1)){
            sum1 = cursum1;
            sum2 = cursum2;
        }
    }
    return {sum1, sum2};
}

diamgr find_gr_dim(int ver){
    if (v[ver].size() == 0){
        diamgr infogr(ver, ver, 0, 0, 0);
        return infogr;
    }
    int s = Dijkstra(ver);
    int f = Dijkstra(s);
    memset(parsum, 0, sizeof(parsum));
    int cntver = init_parsums(s, f, parsum);
    pair<int, int> sums = find_mindif(cntver, parsum);
    diamgr infogr(s, f, sums.first + sums.second, sums.first, sums.second);
    return infogr;
}

inline void subtask123(int *a, int *b, int *t){
    init_vectors(a, b, t);
    diamgr info1, info2;
    for (int i = 0; i < n; ++i)
        if (!checkver[i]){
            if (info1.s == -1)
                info1 = find_gr_dim(i);
            else info2 = find_gr_dim(i);
        }
    anscost = info1.cost;
    anscost = max(anscost, info2.cost);
    anscost = max(anscost, max(info1.sum1, info1.sum2) + max (info2.sum1, info2.sum2));
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    n = N;
    m = M;
    lprice = L;
    //subtask1(A, B, T);
  	subtask123(A, B, T);
    return anscost;
}

Compilation message

dreaming.cpp: In function 'int init_parsums(int, int, int*)':
dreaming.cpp:93:18: warning: unused variable 'prev' [-Wunused-variable]
   93 |     int cur = f, prev = -1;
      |                  ^~~~

Subtask #1
0 / 14.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 23.0

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

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1051 ms 8540 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

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