Submission #806437

#	Time	Username	Problem	Language	Result	Execution time	Memory
806437		thimote75	Wild Boar (JOI18_wild_boar)	C++14	12 / 100	10098 ms	1048576 KiB

wild_boar

#include <bits/stdc++.h>
#define int long long

using namespace std;

string to_string(string s) { return s; }
template <typename T> string to_string(T v) {
	bool first = true;
	string res = "[";
	for (const auto &x : v) {
		if (!first)
			res += ", ";
		first = false;
		res += to_string(x);
	}
	res += "]";
	return res;
}

template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

void dbg_out() { cout << endl; }
template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) {
	cout << ' ' << to_string(H);
	dbg_out(T...);
}

#ifdef DEBUG
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

template <typename T>
using grid = vector<vector<T>>;
template <typename T>
using space = grid<vector<T>>;

using qi = pair<pair<int, int>, pair<int, int>>;
template <typename T>
using lpq = priority_queue<T, vector<T>, less<T>>;

using idata = vector<int>;
using graph = grid<pair<int, int>>;
graph roads;

idata path;
struct State {
    int source = -1, distance = 1e18, count = 0;

    State next (int cost, int curr, int target) {
        State res;
        res.source   = curr;
        res.distance = target == source ? 1e18 : cost + distance;
        res.count    = count + 1 < path.size() && target == path[count + 1] ? count + 1 : count;
        return res;
    }
};

int N, M, T, L;

int modify (vector<State> &states, State new_state) {
    if (states[0].source == new_state.source) {
        if (new_state.distance >= states[0].distance) return -1;
        states[0].distance = new_state.distance;
        return 0;
    } else if (states[0].distance >= new_state.distance) {
        states[1] = states[0];
        states[0] = new_state;
        return 0;
    } else if (states[1].source == new_state.source) {
        if (new_state.distance >= states[1].distance) return -1;
        states[1].distance = new_state.distance;
        return 1;
    } else if (states[1].distance > new_state.distance) {
        states[1] = new_state;
        return 1;
    }
    return -1;
}
int dijkstra () {
    space<State> dij_state (N, grid<State>(L, vector<State>(2)));
    lpq<qi> q;
    dij_state[path[0]][0][0].distance = 0;
    q.push({ { 0, 0 }, { path[0], 0 } });

    while (q.size() != 0) {
        qi data = q.top(); q.pop();
        int dist = data.first.first;
        int src  = data.first.second;
        int curr = data.second.first;
        int uuid = data.second.second;

        if (dist == 1e18) continue ;

        State st = dij_state[curr][src][uuid];
        if (st.distance != dist) continue ;
    
        for (const auto &road : roads[curr]) {
            int next = road.first; int cost = road.second;
            State nxt_state = st.next( cost, curr, next );

            int res = modify(dij_state[next][nxt_state.count], nxt_state);
            if (res == -1) continue ;

            q.push({ { nxt_state.distance, nxt_state.count }, { next, res } });
        }
    }

    int res = dij_state[path[L - 1]][L - 1][0].distance;
    return res == 1e18 ? -1 : res;
}

signed main () {
    cin >> N >> M >> T >> L;

    roads.resize(N);
    for (int i = 0; i < M; i ++) {
        int a, b, c;
        cin >> a >> b >> c;
        a --; b --;

        roads[a].push_back({ b, c });
        roads[b].push_back({ a, c });
    }

    path.resize(L);

    for (int i = 0; i < L; i ++) {
        cin >> path[i];
        path[i] --;
    }

    for (int i = 0; i < T; i ++) {
        int p, v;
        cin >> p >> v;
        p --; v --;

        path[p] = v;
    
        cout << dijkstra() << "\n";
    }
}

Compilation message (stderr)

wild_boar.cpp: In member function 'State State::next(long long int, long long int, long long int)':
wild_boar.cpp:59:34: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |         res.count    = count + 1 < path.size() && target == path[count + 1] ? count + 1 : count;
      |                        ~~~~~~~~~~^~~~~~~~~~~~~

• Subtask 1: 12 / 12
• Subtask 2: 0 / 35
• Subtask 3: 0 / 15
• Subtask 4: 0 / 38