oj.uz

답안 #1096177

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1096177 2024-10-04T03:57:05 Z RiverFlow 은하철도 (APIO24_train) C++17
5 / 100
 1000 ms 800412 KB 
#include <bits/stdc++.h>

#define nl "\n"
#define no "NO"
#define yes "YES"
#define fi first
#define se second
#define vec vector
#define task "main"
#define _mp make_pair
#define ii pair<int, int>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define evoid(val) return void(cout << val)
#define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
#define FOD(i, b, a) for(int i = (b); i >= (a); --i)
#define unq(x) sort(all(x)); x.resize(unique(all(x)) - x.begin())

using namespace std;

template<typename U, typename V> bool maxi(U &a, V b) {
    if (a < b) { a = b; return 1; } return 0;
}
template<typename U, typename V> bool mini(U &a, V b) {
    if (a > b or a == -1) { a = b; return 1; } return 0;
}

const int N = (int)2e5 + 9;
const int mod = (int)1e9 + 7;

struct edge {
    int a, b, x, y, c;
    edge () {};
    edge (int _a, int _b, int _x, int _y, int _c) {
        a  = _a, b = _b, x = _x, y = _y, c = _c;
    }
};

struct meals {
    int l, r;
    bool operator < (const meals & other) {
        return l < other.l;
    }
} meal[N];

edge e[N];

int n, m, w, land[N];

vector<int> g[N];

namespace SUB1 {
const int W = 10;
const int M = (int)1e3 + 7;

long long dp[M][1 << W];

using pli = pair<long long, ii>;

int ov[M];

long long sol() {
    memset(dp, -1, sizeof dp);

    priority_queue<pli, vec<pli>, greater<pli>> pq;

    dp[m][0] = 0; pq.push(_mp(0, _mp(m, 0)));

    auto intersect = [](int x, int y, int u, int v) -> bool {
        return !(x > v or y < u);
    };
    for(int i = 0; i < m; ++i) {
        for(int j = 0; j < w; ++j) {
            if (intersect(e[i].a, e[i].b, meal[j].l, meal[j].r)) {
                ov[i] |= (1 << j);
            }
        }
    }
    while (!pq.empty()) {
        auto cur = pq.top(); pq.pop();
        int ed = cur.se.fi;
        int mask = cur.se.se;

        if (cur.fi != dp[ed][mask]) continue ;

        int u = e[ed].y;
        int tx = e[ed].b;
        for(int t = 0; t < w; ++t) if ( !(1 & mask >> t) ) {
            if (meal[t].l > e[ed].b and mini(dp[ed][mask ^ (1 << t)], cur.fi + land[u])) {
                pq.push(_mp(cur.fi + land[u], _mp(ed, mask ^ (1 << t))));
            }
        } else
            tx = max(tx, meal[t].l);

        for(int id : g[u]) {
            if (tx <= e[id].a) {
                if (mini(dp[id][mask | ov[id]], cur.fi + e[id].c)) {
                    pq.push(_mp(dp[id][mask | ov[id]], _mp(id, mask | ov[id])));
                }
            }
        }
    }
    long long ans = -1;
    for(int i = 0; i < m; ++i) {
        if (e[i].y == n - 1) {
            for(int mask = 0; mask < (1 << w); ++mask) if (dp[i][mask] != -1) {
                mini(dp[i][mask | ov[i]], dp[i][mask]);
            }
            if (dp[i][(1 << w) - 1] != -1) {
                mini(ans, dp[i][(1 << w) - 1]);
            }
        }
    }
    return ans;
}
};

namespace SUB {

long long dp[N]; //M

vector<int> adj[N];

int deg[N];

long long sol() {
    for(int i = 0; i < m; ++i) {
        int y = e[i].y;
        for(int j : g[y]) {
            if (e[j].a >= e[i].b) {
                adj[i].push_back(j);
                ++deg[j];
            }
        }
    }
    memset(dp, -1, sizeof dp);
    queue<int> q;

    for(int i = 0; i < m; ++i) {
        int u = e[i].x;
        long long cost = e[i].c;
        for(int k = 0; k < w; ++k) if (meal[k].r < e[i].a) cost += land[u];
        if (e[i].x == 0) {
            dp[i] = cost;
        }
        if (deg[i]==0) {
            q.push(i);
        }
    }
//    for(int i = 0; i < m; ++i) cout << dp[i] << ' '; cout << nl;

    while (!q.empty()) {
        int i = q.front(); q.pop();
        int u = e[i].y;
        for(int j : adj[i]) {
            long long cost2 = 0;
            for(int k = 0; k < w; ++k) {
                if (meal[k].l > e[i].b and meal[k].r < e[j].a) {
                    cost2 += land[u];
                }
            }
            --deg[j];
            if (dp[i] != -1)
                mini(dp[j], dp[i] + cost2 + e[j].c);
            if (deg[j] == 0) {
                q.push(j);
            }
        }
    }
    for(int i = 0; i < m; ++i) if (dp[i] != -1) {
        int u = e[i].y;
        for(int k = 0; k < w; ++k) {
            if (meal[k].l > e[i].b) dp[i] += land[u];
        }
    }
//    for(int i = 0; i < m; ++i) cout << dp[i] << ' '; cout << nl;
    long long ans = -1;
    for(int i = 0; i < m; ++i) if (e[i].y == n - 1 and dp[i] != -1) {
        mini(ans, dp[i]);
    }
    return ans;
}
};


long long solve(
    int N, int M, int W,
    vector<int> T, vector<int> X, vector<int> Y,
    vector<int> A, vector<int> B, vector<int> C, vector<int> L, vector<int> R) {

    n = N, m = M, w = W;
    for(int i = 0; i < n; ++i) land[i] = T[i];
    for(int i = 0; i < m; ++i) {
        e[i] = edge(A[i], B[i], X[i], Y[i], C[i]);
        g[X[i]].push_back(i);
    }
    e[m] = edge(0, 0, 0, 0, 0);
    for(int i = 0; i < w; ++i) {
        meal[i].l = L[i], meal[i].r = R[i];
    }
//    if (w <= 10 and m <= 1000) {
//        return SUB1::sol();
//    }
    return SUB::sol();
}
#ifdef LOCAL
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    freopen("main.inp", "r", stdin);
    freopen("main.out", "w", stdout);
  int N, M, W;
  assert(3 == scanf("%d %d %d", &N, &M, &W));
  std::vector<int> t(N), x(M), y(M), a(M), b(M), c(M), l(W), r(W);
  for (int i = 0; i < N; i++)
    assert(1 == scanf("%d", &t[i]));
  for (int i = 0; i < M; i++)
    assert(5 == scanf("%d %d %d %d %d", &x[i], &y[i], &a[i], &b[i], &c[i]));
  for (int i = 0; i < W; i++)
    assert(2 == scanf("%d %d", &l[i], &r[i]));
  printf("%lld", solve(N, M, W, t, x, y, a, b, c, l, r));
}
#endif LOCAL

Compilation message

train.cpp:223:8: warning: extra tokens at end of #endif directive [-Wendif-labels]
  223 | #endif LOCAL
      |        ^~~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 11352 KB Correct.
2 Correct 5 ms 11400 KB Correct.
3 Correct 5 ms 11356 KB Correct.
4 Correct 5 ms 11356 KB Correct.
5 Correct 4 ms 11352 KB Correct.
6 Correct 5 ms 11356 KB Correct.
7 Correct 5 ms 11356 KB Correct.

Subtask #2
0.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 74 ms 27472 KB Correct.
2 Correct 68 ms 28656 KB Correct.
3 Correct 5 ms 11356 KB Correct.
4 Correct 11 ms 13148 KB Correct.
5 Correct 5 ms 11352 KB Correct.
6 Correct 183 ms 57940 KB Correct.
7 Correct 6 ms 11352 KB Correct.
8 Execution timed out 1101 ms 800412 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #3
0.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 74 ms 27472 KB Correct.
2 Correct 68 ms 28656 KB Correct.
3 Correct 5 ms 11356 KB Correct.
4 Correct 11 ms 13148 KB Correct.
5 Correct 5 ms 11352 KB Correct.
6 Correct 183 ms 57940 KB Correct.
7 Correct 6 ms 11352 KB Correct.
8 Execution timed out 1101 ms 800412 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 11352 KB Correct.
2 Correct 5 ms 11400 KB Correct.
3 Correct 5 ms 11356 KB Correct.
4 Correct 5 ms 11356 KB Correct.
5 Correct 4 ms 11352 KB Correct.
6 Correct 5 ms 11356 KB Correct.
7 Correct 5 ms 11356 KB Correct.
8 Correct 74 ms 27472 KB Correct.
9 Correct 68 ms 28656 KB Correct.
10 Correct 5 ms 11356 KB Correct.
11 Correct 11 ms 13148 KB Correct.
12 Correct 5 ms 11352 KB Correct.
13 Correct 183 ms 57940 KB Correct.
14 Correct 6 ms 11352 KB Correct.
15 Execution timed out 1101 ms 800412 KB Time limit exceeded
16 Halted 0 ms 0 KB -