oj.uz

Submission #806743

# Submission time Handle Problem Language Result Execution time Memory
806743 2023-08-04T09:28:30 Z thimote75 Wild Boar (JOI18_wild_boar) C++14
47 / 100
 17406 ms 1048576 KB 
#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

struct State {
    int source = -1; int target = -1; int distance = 1e18;
    State next (int node, int next, int cost) {
        State st;
        st.source   = source == -1 ? next : source;
        st.distance = cost + distance;
        if (next == target) st.distance = 1e18;
        st.target   = node;

        return st;
    }
    bool operator< (const State &other) const {
        return distance < other.distance;
    }
};
struct CNT {
    map<int, int> m;
    int get (int x) {
        if (m.find(x) == m.end()) return 0;
        return (*m.find(x)).second;
    }
    int pop (int x) {
        if (m.find(x) == m.end()) return 0;
        int res = (*m.find(x)).second; m.erase(x);
        return res;
    }
    void insert (int x) {
        int f = pop(x);
        m.insert({ x, f + 1 });
    }
};

string to_string (State state) {
    if (state.distance == 1e18)
        return "State#";
    return "State[" + to_string(state.source + 1) + " => " + to_string(state.target + 1) + ", " + to_string(state.distance) + "]";
}

struct Matrix {
    vector<State> pcc;
    CNT lst;
    CNT fst;
    set<pair<int, int>> s;
    
    bool append (State state, bool apply = true) {
        if (pcc.size() >= 9) return false;
        if (lst.get(state.target) >= 3) return false;
        if (fst.get(state.source) >= 3) return false;
        if (s.find({ state.source, state.target }) != s.end()) return false;

        if (apply) {
            lst.insert(state.target);
            fst.insert(state.source);
            pcc.push_back(state);
            s.insert({ state.source, state.target });
        }
        return true;
    }

    vector<State> all () {
        return pcc;
    }
    int answer () {
        return pcc.size() == 0 ? -1 : pcc[0].distance;
    }

    Matrix merge (Matrix &other) {
        Matrix res;

        vector<State> all_states;
        for (State s1: all()) {
            for (State s2: other.all()) {
                State s3;
                if (s1.target == s2.source) continue ;

                s3.source   = s1.source;
                s3.target   = s2.target;
                s3.distance = s1.distance + s2.distance;

                all_states.push_back(s3);
            }
        }

        sort(all_states.begin(), all_states.end());
        for (State s : all_states)
            res.append(s);
        
        return res;
    }
};
string to_string (Matrix matrix) {
    return "Mat" + to_string(matrix.all());
}
using vMatrix = vector<Matrix>;
using ti = pair<pair<int, int>, State>;
using pq = priority_queue<ti, vector<ti>, greater<ti>>;
template<typename T>
using grid  = vector<vector<T>>;
using idata = vector<int>;

using graph = grid<pair<int, int>>;

int N, M, T, L;
graph roads;

vMatrix dijkstra (int start) {
    pq q;

    vMatrix matrices(N);
    State startState;
    startState.distance = 0;
    q.push({ { 0, start }, startState });
    
    dbg(start);
    while (q.size() != 0) {
        const auto data = q.top(); q.pop();
        State state = data.second;
        int node = data.first.second;

        //if (state.distance >= 1e18) continue ;

        dbg(node, state.distance);

        if (!matrices[node].append( state )) continue ;
    
        for (const auto & road : roads[node]) {
            int next = road.first; int cost = road.second;

            State nextState = state.next(node, next, cost);
            if (!matrices[next].append(nextState, false)) continue ;

            q.push({ { nextState.distance, next }, nextState });
        }
    }

    for (Matrix &matrix : matrices) {
        map<int, int>().swap(matrix.fst.m);
        map<int, int>().swap(matrix.lst.m);
        set<pair<int, int>>().swap(matrix.s);
    }

    return matrices;
}

grid<Matrix> matrixGrid;

signed main () {
    ios_base::sync_with_stdio(false); cin.tie(NULL);

    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 });
    }

    for (int i = 0; i < N; i ++)
        matrixGrid.push_back( dijkstra(i) );
    
    idata DV(L);
    for (int i = 0; i < L; i ++) {
        cin >> DV[i];
        DV[i] --;
    }

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

        DV[p] = v;

        Matrix result = matrixGrid[DV[0]][DV[1]];

        dbg(result);

        for (int j = 2; j < L; j ++) {
            dbg(DV[j - 1] + 1, DV[j] + 1);
            result = result.merge(matrixGrid[DV[j - 1]][DV[j]]);
        }

        int answer = result.answer();
        if (answer == 1e18) answer = -1;
        cout << answer << "\n";
    }
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 324 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 312 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 320 KB Output is correct
16 Correct 1 ms 324 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 2 ms 424 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 324 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 312 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 320 KB Output is correct
16 Correct 1 ms 324 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 2 ms 424 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 4 ms 468 KB Output is correct
27 Correct 25 ms 4260 KB Output is correct
28 Correct 24 ms 4216 KB Output is correct
29 Correct 580 ms 7452 KB Output is correct
30 Correct 616 ms 6960 KB Output is correct
31 Correct 540 ms 7184 KB Output is correct
32 Correct 501 ms 7348 KB Output is correct
33 Correct 611 ms 13452 KB Output is correct
34 Correct 609 ms 13572 KB Output is correct
35 Correct 492 ms 12636 KB Output is correct
36 Correct 521 ms 12072 KB Output is correct
37 Correct 651 ms 13920 KB Output is correct
38 Correct 594 ms 19228 KB Output is correct
39 Correct 639 ms 16432 KB Output is correct
40 Correct 523 ms 19300 KB Output is correct
41 Correct 478 ms 19348 KB Output is correct
42 Correct 560 ms 19624 KB Output is correct
43 Correct 417 ms 23528 KB Output is correct
44 Correct 462 ms 23424 KB Output is correct
45 Correct 288 ms 26272 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 324 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 312 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 320 KB Output is correct
16 Correct 1 ms 324 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 2 ms 424 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 4 ms 468 KB Output is correct
27 Correct 25 ms 4260 KB Output is correct
28 Correct 24 ms 4216 KB Output is correct
29 Correct 580 ms 7452 KB Output is correct
30 Correct 616 ms 6960 KB Output is correct
31 Correct 540 ms 7184 KB Output is correct
32 Correct 501 ms 7348 KB Output is correct
33 Correct 611 ms 13452 KB Output is correct
34 Correct 609 ms 13572 KB Output is correct
35 Correct 492 ms 12636 KB Output is correct
36 Correct 521 ms 12072 KB Output is correct
37 Correct 651 ms 13920 KB Output is correct
38 Correct 594 ms 19228 KB Output is correct
39 Correct 639 ms 16432 KB Output is correct
40 Correct 523 ms 19300 KB Output is correct
41 Correct 478 ms 19348 KB Output is correct
42 Correct 560 ms 19624 KB Output is correct
43 Correct 417 ms 23528 KB Output is correct
44 Correct 462 ms 23424 KB Output is correct
45 Correct 288 ms 26272 KB Output is correct
46 Correct 416 ms 22444 KB Output is correct
47 Correct 4230 ms 142076 KB Output is correct
48 Correct 6872 ms 297240 KB Output is correct
49 Correct 9304 ms 447300 KB Output is correct
50 Correct 9764 ms 454668 KB Output is correct
51 Correct 9641 ms 462204 KB Output is correct
52 Correct 12954 ms 518132 KB Output is correct
53 Correct 13056 ms 519740 KB Output is correct
54 Correct 12900 ms 516104 KB Output is correct
55 Correct 13248 ms 514196 KB Output is correct
56 Correct 14560 ms 594528 KB Output is correct
57 Correct 14828 ms 681348 KB Output is correct
58 Correct 15576 ms 742524 KB Output is correct
59 Correct 16783 ms 819000 KB Output is correct
60 Correct 17406 ms 877780 KB Output is correct
61 Correct 17053 ms 933668 KB Output is correct
62 Correct 16993 ms 982232 KB Output is correct
63 Correct 16143 ms 1021252 KB Output is correct
64 Runtime error 8309 ms 1048576 KB Execution killed with signal 9
65 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 324 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 312 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 320 KB Output is correct
16 Correct 1 ms 324 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 2 ms 424 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 4 ms 468 KB Output is correct
27 Correct 25 ms 4260 KB Output is correct
28 Correct 24 ms 4216 KB Output is correct
29 Correct 580 ms 7452 KB Output is correct
30 Correct 616 ms 6960 KB Output is correct
31 Correct 540 ms 7184 KB Output is correct
32 Correct 501 ms 7348 KB Output is correct
33 Correct 611 ms 13452 KB Output is correct
34 Correct 609 ms 13572 KB Output is correct
35 Correct 492 ms 12636 KB Output is correct
36 Correct 521 ms 12072 KB Output is correct
37 Correct 651 ms 13920 KB Output is correct
38 Correct 594 ms 19228 KB Output is correct
39 Correct 639 ms 16432 KB Output is correct
40 Correct 523 ms 19300 KB Output is correct
41 Correct 478 ms 19348 KB Output is correct
42 Correct 560 ms 19624 KB Output is correct
43 Correct 417 ms 23528 KB Output is correct
44 Correct 462 ms 23424 KB Output is correct
45 Correct 288 ms 26272 KB Output is correct
46 Correct 416 ms 22444 KB Output is correct
47 Correct 4230 ms 142076 KB Output is correct
48 Correct 6872 ms 297240 KB Output is correct
49 Correct 9304 ms 447300 KB Output is correct
50 Correct 9764 ms 454668 KB Output is correct
51 Correct 9641 ms 462204 KB Output is correct
52 Correct 12954 ms 518132 KB Output is correct
53 Correct 13056 ms 519740 KB Output is correct
54 Correct 12900 ms 516104 KB Output is correct
55 Correct 13248 ms 514196 KB Output is correct
56 Correct 14560 ms 594528 KB Output is correct
57 Correct 14828 ms 681348 KB Output is correct
58 Correct 15576 ms 742524 KB Output is correct
59 Correct 16783 ms 819000 KB Output is correct
60 Correct 17406 ms 877780 KB Output is correct
61 Correct 17053 ms 933668 KB Output is correct
62 Correct 16993 ms 982232 KB Output is correct
63 Correct 16143 ms 1021252 KB Output is correct
64 Runtime error 8309 ms 1048576 KB Execution killed with signal 9
65 Halted 0 ms 0 KB -