oj.uz

답안 #60846

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
60846 2018-07-24T20:32:26 Z SpeedOfMagic Pinball (JOI14_pinball) C++17
51 / 100
 1000 ms 159112 KB 
/** MIT License Copyright (c) 2018 Vasilyev Daniil **/
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
template<typename T> using v = vector<T>;
#define int long long
typedef string str;
typedef vector<int> vint;
#define rep(a, l, r) for(int a = (l); a < (r); a++)
#define pb push_back
#define sz(a) ((int) a.size())
const long long inf = 4611686018427387903; //2^62 - 1
#if 0  //FileIO
const string fileName = "";
ifstream fin ((fileName == "" ? "input.txt"  : fileName + ".in" ));
ofstream fout((fileName == "" ? "output.txt" : fileName + ".out"));
#define get fin>>
#define put fout<<
#else
#define get cin>>
#define put cout<<
#endif
#define eol put endl
void read() {}     template<typename Arg,typename... Args> void read (Arg& arg,Args&... args){get (arg)     ;read(args...) ;}
void print(){}     template<typename Arg,typename... Args> void print(Arg  arg,Args...  args){put (arg)<<" ";print(args...);}
void debug(){eol;} template<typename Arg,typename... Args> void debug(Arg  arg,Args...  args){put (arg)<<" ";debug(args...);}
int getInt(){int a; get a; return a;}
//code goes here
const int M = 1e5 + 1;
vint g[M];
int devices[M][4];
int m = 1, n;
vint calcDistance(int d) {
    vint res(m, inf);
    res[d] = devices[d][3];
    priority_queue<pair<int, int>> dijkstra;
    dijkstra.push({-devices[d][3], d});
    while (!dijkstra.empty()) {
        int cur = dijkstra.top().second;
        int cost = -dijkstra.top().first;
        dijkstra.pop();
        if (cost != res[cur])
            continue;
        //debug(cost, cur);

        for (int i : g[cur])
            if (res[i] > cost + devices[i][3]) {
                res[i] = devices[i][3] + cost;
                dijkstra.push({-res[i], i});
            }
    }

    return res;
}

void run() {
    read(m, n);
    vint firsts, lasts;
    rep(i, 0, m) {
        read(devices[i][0], devices[i][1], devices[i][2], devices[i][3]);
        if (devices[i][0] == 1)
            firsts.pb(i);
        if (devices[i][1] == n)
            lasts.pb(i);

        rep(j, 0, i)
            if (devices[i][0] <= devices[j][2] && devices[j][2] <= devices[i][1])
                g[j].pb(i);
    }

    int posDists[m];
    rep(i, 0, m)
        posDists[i] = inf;

    for (int i : firsts) {
        vint dists = calcDistance(i);
        rep(j, 0, m)
            posDists[j] = min(posDists[j], dists[j]);
    }

    int ans = inf;
    for (int i : lasts) {
        vint dists = calcDistance(i);
        rep(j, 0, m)
            ans = min(ans, dists[j] + posDists[j] - devices[j][3]);
    }
    if (ans >= inf)
        put - 1;
    else
        put ans;
}

int32_t main() {srand(time(0)); ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); put fixed; put setprecision(15); run(); return 0;}

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 2680 KB Output is correct
2 Correct 5 ms 2680 KB Output is correct
3 Correct 5 ms 2724 KB Output is correct
4 Correct 4 ms 2776 KB Output is correct
5 Correct 4 ms 2976 KB Output is correct
6 Correct 5 ms 2976 KB Output is correct
7 Correct 4 ms 2988 KB Output is correct
8 Correct 6 ms 2992 KB Output is correct

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 2680 KB Output is correct
2 Correct 5 ms 2680 KB Output is correct
3 Correct 5 ms 2724 KB Output is correct
4 Correct 4 ms 2776 KB Output is correct
5 Correct 4 ms 2976 KB Output is correct
6 Correct 5 ms 2976 KB Output is correct
7 Correct 4 ms 2988 KB Output is correct
8 Correct 6 ms 2992 KB Output is correct
9 Correct 6 ms 3252 KB Output is correct
10 Correct 6 ms 3256 KB Output is correct
11 Correct 6 ms 3280 KB Output is correct
12 Correct 7 ms 3280 KB Output is correct
13 Correct 6 ms 3280 KB Output is correct
14 Correct 7 ms 3280 KB Output is correct

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 2680 KB Output is correct
2 Correct 5 ms 2680 KB Output is correct
3 Correct 5 ms 2724 KB Output is correct
4 Correct 4 ms 2776 KB Output is correct
5 Correct 4 ms 2976 KB Output is correct
6 Correct 5 ms 2976 KB Output is correct
7 Correct 4 ms 2988 KB Output is correct
8 Correct 6 ms 2992 KB Output is correct
9 Correct 6 ms 3252 KB Output is correct
10 Correct 6 ms 3256 KB Output is correct
11 Correct 6 ms 3280 KB Output is correct
12 Correct 7 ms 3280 KB Output is correct
13 Correct 6 ms 3280 KB Output is correct
14 Correct 7 ms 3280 KB Output is correct
15 Correct 7 ms 3280 KB Output is correct
16 Correct 8 ms 3532 KB Output is correct
17 Correct 23 ms 5540 KB Output is correct
18 Correct 84 ms 5632 KB Output is correct
19 Correct 18 ms 5672 KB Output is correct
20 Correct 25 ms 5728 KB Output is correct
21 Correct 7 ms 5728 KB Output is correct
22 Correct 12 ms 5728 KB Output is correct
23 Correct 9 ms 5728 KB Output is correct
24 Correct 11 ms 5728 KB Output is correct

Subtask #4
0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 2680 KB Output is correct
2 Correct 5 ms 2680 KB Output is correct
3 Correct 5 ms 2724 KB Output is correct
4 Correct 4 ms 2776 KB Output is correct
5 Correct 4 ms 2976 KB Output is correct
6 Correct 5 ms 2976 KB Output is correct
7 Correct 4 ms 2988 KB Output is correct
8 Correct 6 ms 2992 KB Output is correct
9 Correct 6 ms 3252 KB Output is correct
10 Correct 6 ms 3256 KB Output is correct
11 Correct 6 ms 3280 KB Output is correct
12 Correct 7 ms 3280 KB Output is correct
13 Correct 6 ms 3280 KB Output is correct
14 Correct 7 ms 3280 KB Output is correct
15 Correct 7 ms 3280 KB Output is correct
16 Correct 8 ms 3532 KB Output is correct
17 Correct 23 ms 5540 KB Output is correct
18 Correct 84 ms 5632 KB Output is correct
19 Correct 18 ms 5672 KB Output is correct
20 Correct 25 ms 5728 KB Output is correct
21 Correct 7 ms 5728 KB Output is correct
22 Correct 12 ms 5728 KB Output is correct
23 Correct 9 ms 5728 KB Output is correct
24 Correct 11 ms 5728 KB Output is correct
25 Execution timed out 1071 ms 159112 KB Time limit exceeded
26 Halted 0 ms 0 KB -