oj.uz

Submission #806757

# Submission time Handle Problem Language Result Execution time Memory
806757 2023-08-04T09:35:51 Z thimote75 Wild Boar (JOI18_wild_boar) C++14
47 / 100
 18000 ms 756336 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) + "]";
}

CNT map_buffer[5000]; int buffer_pos = 0;
CNT* get_buffer () {
    return map_buffer + (buffer_pos ++);
}

struct Matrix {
    vector<State> pcc;
    CNT* lst = get_buffer();
    CNT* fst = get_buffer();
    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;
    }
    void clear () {
        fst->m.clear();
        lst->m.clear();
        set<pair<int, int>>().swap(s);
    }

    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);
        
        res.clear();
        buffer_pos = 0;
        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)
        matrix.clear();

    buffer_pos = 0;
    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 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 560 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 560 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 556 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Correct 1 ms 596 KB Output is correct
12 Correct 1 ms 560 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 1 ms 556 KB Output is correct
15 Correct 1 ms 596 KB Output is correct
16 Correct 1 ms 596 KB Output is correct
17 Correct 1 ms 560 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 1 ms 556 KB Output is correct
20 Correct 1 ms 468 KB Output is correct
21 Correct 1 ms 468 KB Output is correct
22 Correct 1 ms 468 KB Output is correct
23 Correct 1 ms 468 KB Output is correct
24 Correct 1 ms 556 KB Output is correct
25 Correct 1 ms 468 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 560 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 560 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 556 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Correct 1 ms 596 KB Output is correct
12 Correct 1 ms 560 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 1 ms 556 KB Output is correct
15 Correct 1 ms 596 KB Output is correct
16 Correct 1 ms 596 KB Output is correct
17 Correct 1 ms 560 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 1 ms 556 KB Output is correct
20 Correct 1 ms 468 KB Output is correct
21 Correct 1 ms 468 KB Output is correct
22 Correct 1 ms 468 KB Output is correct
23 Correct 1 ms 468 KB Output is correct
24 Correct 1 ms 556 KB Output is correct
25 Correct 1 ms 468 KB Output is correct
26 Correct 4 ms 724 KB Output is correct
27 Correct 25 ms 3600 KB Output is correct
28 Correct 25 ms 3588 KB Output is correct
29 Correct 580 ms 6772 KB Output is correct
30 Correct 612 ms 6316 KB Output is correct
31 Correct 517 ms 6604 KB Output is correct
32 Correct 510 ms 6676 KB Output is correct
33 Correct 641 ms 11804 KB Output is correct
34 Correct 674 ms 11932 KB Output is correct
35 Correct 506 ms 11052 KB Output is correct
36 Correct 535 ms 10428 KB Output is correct
37 Correct 687 ms 12288 KB Output is correct
38 Correct 639 ms 16100 KB Output is correct
39 Correct 667 ms 13416 KB Output is correct
40 Correct 556 ms 16224 KB Output is correct
41 Correct 503 ms 16232 KB Output is correct
42 Correct 573 ms 15660 KB Output is correct
43 Correct 413 ms 18636 KB Output is correct
44 Correct 420 ms 18592 KB Output is correct
45 Correct 290 ms 19284 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 560 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 560 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 556 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Correct 1 ms 596 KB Output is correct
12 Correct 1 ms 560 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 1 ms 556 KB Output is correct
15 Correct 1 ms 596 KB Output is correct
16 Correct 1 ms 596 KB Output is correct
17 Correct 1 ms 560 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 1 ms 556 KB Output is correct
20 Correct 1 ms 468 KB Output is correct
21 Correct 1 ms 468 KB Output is correct
22 Correct 1 ms 468 KB Output is correct
23 Correct 1 ms 468 KB Output is correct
24 Correct 1 ms 556 KB Output is correct
25 Correct 1 ms 468 KB Output is correct
26 Correct 4 ms 724 KB Output is correct
27 Correct 25 ms 3600 KB Output is correct
28 Correct 25 ms 3588 KB Output is correct
29 Correct 580 ms 6772 KB Output is correct
30 Correct 612 ms 6316 KB Output is correct
31 Correct 517 ms 6604 KB Output is correct
32 Correct 510 ms 6676 KB Output is correct
33 Correct 641 ms 11804 KB Output is correct
34 Correct 674 ms 11932 KB Output is correct
35 Correct 506 ms 11052 KB Output is correct
36 Correct 535 ms 10428 KB Output is correct
37 Correct 687 ms 12288 KB Output is correct
38 Correct 639 ms 16100 KB Output is correct
39 Correct 667 ms 13416 KB Output is correct
40 Correct 556 ms 16224 KB Output is correct
41 Correct 503 ms 16232 KB Output is correct
42 Correct 573 ms 15660 KB Output is correct
43 Correct 413 ms 18636 KB Output is correct
44 Correct 420 ms 18592 KB Output is correct
45 Correct 290 ms 19284 KB Output is correct
46 Correct 403 ms 19568 KB Output is correct
47 Correct 4205 ms 122680 KB Output is correct
48 Correct 7125 ms 246892 KB Output is correct
49 Correct 9998 ms 369232 KB Output is correct
50 Correct 9868 ms 376488 KB Output is correct
51 Correct 9656 ms 384164 KB Output is correct
52 Correct 13103 ms 440148 KB Output is correct
53 Correct 13061 ms 441688 KB Output is correct
54 Correct 12851 ms 438020 KB Output is correct
55 Correct 12816 ms 436172 KB Output is correct
56 Correct 14053 ms 500112 KB Output is correct
57 Correct 15807 ms 568768 KB Output is correct
58 Correct 16624 ms 610460 KB Output is correct
59 Correct 17333 ms 665676 KB Output is correct
60 Correct 17553 ms 701932 KB Output is correct
61 Correct 17794 ms 733580 KB Output is correct
62 Execution timed out 18087 ms 756336 KB Time limit exceeded
63 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 560 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 560 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 556 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Correct 1 ms 596 KB Output is correct
12 Correct 1 ms 560 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 1 ms 556 KB Output is correct
15 Correct 1 ms 596 KB Output is correct
16 Correct 1 ms 596 KB Output is correct
17 Correct 1 ms 560 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 1 ms 556 KB Output is correct
20 Correct 1 ms 468 KB Output is correct
21 Correct 1 ms 468 KB Output is correct
22 Correct 1 ms 468 KB Output is correct
23 Correct 1 ms 468 KB Output is correct
24 Correct 1 ms 556 KB Output is correct
25 Correct 1 ms 468 KB Output is correct
26 Correct 4 ms 724 KB Output is correct
27 Correct 25 ms 3600 KB Output is correct
28 Correct 25 ms 3588 KB Output is correct
29 Correct 580 ms 6772 KB Output is correct
30 Correct 612 ms 6316 KB Output is correct
31 Correct 517 ms 6604 KB Output is correct
32 Correct 510 ms 6676 KB Output is correct
33 Correct 641 ms 11804 KB Output is correct
34 Correct 674 ms 11932 KB Output is correct
35 Correct 506 ms 11052 KB Output is correct
36 Correct 535 ms 10428 KB Output is correct
37 Correct 687 ms 12288 KB Output is correct
38 Correct 639 ms 16100 KB Output is correct
39 Correct 667 ms 13416 KB Output is correct
40 Correct 556 ms 16224 KB Output is correct
41 Correct 503 ms 16232 KB Output is correct
42 Correct 573 ms 15660 KB Output is correct
43 Correct 413 ms 18636 KB Output is correct
44 Correct 420 ms 18592 KB Output is correct
45 Correct 290 ms 19284 KB Output is correct
46 Correct 403 ms 19568 KB Output is correct
47 Correct 4205 ms 122680 KB Output is correct
48 Correct 7125 ms 246892 KB Output is correct
49 Correct 9998 ms 369232 KB Output is correct
50 Correct 9868 ms 376488 KB Output is correct
51 Correct 9656 ms 384164 KB Output is correct
52 Correct 13103 ms 440148 KB Output is correct
53 Correct 13061 ms 441688 KB Output is correct
54 Correct 12851 ms 438020 KB Output is correct
55 Correct 12816 ms 436172 KB Output is correct
56 Correct 14053 ms 500112 KB Output is correct
57 Correct 15807 ms 568768 KB Output is correct
58 Correct 16624 ms 610460 KB Output is correct
59 Correct 17333 ms 665676 KB Output is correct
60 Correct 17553 ms 701932 KB Output is correct
61 Correct 17794 ms 733580 KB Output is correct
62 Execution timed out 18087 ms 756336 KB Time limit exceeded
63 Halted 0 ms 0 KB -