oj.uz

Submission #806814

# Submission time Handle Problem Language Result Execution time Memory
806814 2023-08-04T10:03:18 Z thimote75 Wild Boar (JOI18_wild_boar) C++14
62 / 100
 18000 ms 978432 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;
    }
};

const int MAXN = 2010;
struct CNT {
    signed dp[MAXN];
    signed lp[MAXN];
    signed vp[MAXN];
    int stage = 1;
    CNT () {
        for (int i = 0; i < MAXN; i ++)
            vp[i] = 0;
    }
    void clear () {
        stage ++;
    }
    void check (int node) {
        if (vp[node] != stage) {
            vp[node] = stage;
            lp[node] = dp[node];
        }
    } 
    int get (int x) {
        if (x == -1) return 0;
        check(x);
        return dp[x] - lp[x];
    }
    void insert (int x) {
        if (x == -1) return ;
        check(x);
        dp[x] ++;
    }
};

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 () {
  	if (buffer_pos >= 5000) buffer_pos = 0;
    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->clear();
        lst->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;
}

struct SegTree {
    vector<Matrix> tree;

    int size, start, height;

    SegTree (int _s) {
        size   = _s;
        height = ceil(log2(size));
        start  = 1 << height;

        tree.resize(start << 1);

        for (Matrix m: tree) m.clear();
        buffer_pos = 0;
    }
    void modify (int node, Matrix &mat) {
        node += start;
        tree[node] = mat;
        node >>= 1;

        while (node != 0) {
            tree[node] = tree[node * 2].merge(tree[node * 2 + 1]);
            node >>= 1;
        }
    }
    Matrix query (int right) {
        vector<int> queries;

        right += start;
        int limit = start;
        while (limit < right) {
            if ((right & 1) == 0) queries.push_back(right);

            right = (right - 1) >> 1;
            limit = limit >> 1;
        }

        if (limit == right) queries.push_back(right);

        reverse(queries.begin(), queries.end());

        Matrix mat = tree[queries[0]];
        for (int i = 1; i < queries.size(); i ++)
            mat = mat.merge( tree[queries[i]] );
        
        buffer_pos = 0;
        return mat;
    }
};

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

    SegTree tree(L - 1);
    for (int i = 1; i < L; i ++)
        tree.modify(i - 1, matrixGrid[DV[i - 1]][DV[i]]);

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

        DV[p] = v;
        if (p != 0) tree.modify(p - 1, matrixGrid[DV[p - 1]][DV[p]]);
        if (p != L - 1) tree.modify(p, matrixGrid[DV[p]][DV[p + 1]]);
        
        Matrix result = tree.query(L - 2);

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

Compilation message

wild_boar.cpp: In member function 'Matrix SegTree::query(long long int)':
wild_boar.cpp:250:27: 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]
  250 |         for (int i = 1; i < queries.size(); i ++)
      |                         ~~^~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 59604 KB Output is correct
2 Correct 23 ms 59628 KB Output is correct
3 Correct 24 ms 59724 KB Output is correct
4 Correct 22 ms 59632 KB Output is correct
5 Correct 22 ms 59604 KB Output is correct
6 Correct 23 ms 59596 KB Output is correct
7 Correct 26 ms 59668 KB Output is correct
8 Correct 23 ms 59568 KB Output is correct
9 Correct 22 ms 59604 KB Output is correct
10 Correct 22 ms 59604 KB Output is correct
11 Correct 22 ms 59616 KB Output is correct
12 Correct 22 ms 59604 KB Output is correct
13 Correct 23 ms 59616 KB Output is correct
14 Correct 24 ms 59580 KB Output is correct
15 Correct 23 ms 59604 KB Output is correct
16 Correct 26 ms 59604 KB Output is correct
17 Correct 23 ms 59604 KB Output is correct
18 Correct 25 ms 59604 KB Output is correct
19 Correct 27 ms 59656 KB Output is correct
20 Correct 25 ms 59696 KB Output is correct
21 Correct 22 ms 59624 KB Output is correct
22 Correct 22 ms 59604 KB Output is correct
23 Correct 22 ms 59616 KB Output is correct
24 Correct 23 ms 59648 KB Output is correct
25 Correct 26 ms 59600 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 59604 KB Output is correct
2 Correct 23 ms 59628 KB Output is correct
3 Correct 24 ms 59724 KB Output is correct
4 Correct 22 ms 59632 KB Output is correct
5 Correct 22 ms 59604 KB Output is correct
6 Correct 23 ms 59596 KB Output is correct
7 Correct 26 ms 59668 KB Output is correct
8 Correct 23 ms 59568 KB Output is correct
9 Correct 22 ms 59604 KB Output is correct
10 Correct 22 ms 59604 KB Output is correct
11 Correct 22 ms 59616 KB Output is correct
12 Correct 22 ms 59604 KB Output is correct
13 Correct 23 ms 59616 KB Output is correct
14 Correct 24 ms 59580 KB Output is correct
15 Correct 23 ms 59604 KB Output is correct
16 Correct 26 ms 59604 KB Output is correct
17 Correct 23 ms 59604 KB Output is correct
18 Correct 25 ms 59604 KB Output is correct
19 Correct 27 ms 59656 KB Output is correct
20 Correct 25 ms 59696 KB Output is correct
21 Correct 22 ms 59624 KB Output is correct
22 Correct 22 ms 59604 KB Output is correct
23 Correct 22 ms 59616 KB Output is correct
24 Correct 23 ms 59648 KB Output is correct
25 Correct 26 ms 59600 KB Output is correct
26 Correct 30 ms 60004 KB Output is correct
27 Correct 146 ms 99368 KB Output is correct
28 Correct 163 ms 99760 KB Output is correct
29 Correct 634 ms 149288 KB Output is correct
30 Correct 620 ms 149956 KB Output is correct
31 Correct 552 ms 150104 KB Output is correct
32 Correct 529 ms 150208 KB Output is correct
33 Correct 619 ms 148056 KB Output is correct
34 Correct 617 ms 148808 KB Output is correct
35 Correct 492 ms 155080 KB Output is correct
36 Correct 602 ms 154364 KB Output is correct
37 Correct 657 ms 151356 KB Output is correct
38 Correct 566 ms 142428 KB Output is correct
39 Correct 683 ms 158084 KB Output is correct
40 Correct 550 ms 142696 KB Output is correct
41 Correct 575 ms 142368 KB Output is correct
42 Correct 556 ms 160760 KB Output is correct
43 Correct 465 ms 135516 KB Output is correct
44 Correct 472 ms 135132 KB Output is correct
45 Correct 354 ms 126460 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 59604 KB Output is correct
2 Correct 23 ms 59628 KB Output is correct
3 Correct 24 ms 59724 KB Output is correct
4 Correct 22 ms 59632 KB Output is correct
5 Correct 22 ms 59604 KB Output is correct
6 Correct 23 ms 59596 KB Output is correct
7 Correct 26 ms 59668 KB Output is correct
8 Correct 23 ms 59568 KB Output is correct
9 Correct 22 ms 59604 KB Output is correct
10 Correct 22 ms 59604 KB Output is correct
11 Correct 22 ms 59616 KB Output is correct
12 Correct 22 ms 59604 KB Output is correct
13 Correct 23 ms 59616 KB Output is correct
14 Correct 24 ms 59580 KB Output is correct
15 Correct 23 ms 59604 KB Output is correct
16 Correct 26 ms 59604 KB Output is correct
17 Correct 23 ms 59604 KB Output is correct
18 Correct 25 ms 59604 KB Output is correct
19 Correct 27 ms 59656 KB Output is correct
20 Correct 25 ms 59696 KB Output is correct
21 Correct 22 ms 59624 KB Output is correct
22 Correct 22 ms 59604 KB Output is correct
23 Correct 22 ms 59616 KB Output is correct
24 Correct 23 ms 59648 KB Output is correct
25 Correct 26 ms 59600 KB Output is correct
26 Correct 30 ms 60004 KB Output is correct
27 Correct 146 ms 99368 KB Output is correct
28 Correct 163 ms 99760 KB Output is correct
29 Correct 634 ms 149288 KB Output is correct
30 Correct 620 ms 149956 KB Output is correct
31 Correct 552 ms 150104 KB Output is correct
32 Correct 529 ms 150208 KB Output is correct
33 Correct 619 ms 148056 KB Output is correct
34 Correct 617 ms 148808 KB Output is correct
35 Correct 492 ms 155080 KB Output is correct
36 Correct 602 ms 154364 KB Output is correct
37 Correct 657 ms 151356 KB Output is correct
38 Correct 566 ms 142428 KB Output is correct
39 Correct 683 ms 158084 KB Output is correct
40 Correct 550 ms 142696 KB Output is correct
41 Correct 575 ms 142368 KB Output is correct
42 Correct 556 ms 160760 KB Output is correct
43 Correct 465 ms 135516 KB Output is correct
44 Correct 472 ms 135132 KB Output is correct
45 Correct 354 ms 126460 KB Output is correct
46 Correct 351 ms 80272 KB Output is correct
47 Correct 3852 ms 269752 KB Output is correct
48 Correct 7190 ms 403280 KB Output is correct
49 Correct 9445 ms 530048 KB Output is correct
50 Correct 10026 ms 537408 KB Output is correct
51 Correct 9485 ms 544892 KB Output is correct
52 Correct 12906 ms 591824 KB Output is correct
53 Correct 12720 ms 593556 KB Output is correct
54 Correct 12893 ms 589444 KB Output is correct
55 Correct 12570 ms 586664 KB Output is correct
56 Correct 14040 ms 650408 KB Output is correct
57 Correct 15539 ms 719668 KB Output is correct
58 Correct 15837 ms 762724 KB Output is correct
59 Correct 16659 ms 817424 KB Output is correct
60 Correct 15197 ms 852004 KB Output is correct
61 Correct 15602 ms 882492 KB Output is correct
62 Correct 16847 ms 903700 KB Output is correct
63 Correct 16638 ms 913508 KB Output is correct
64 Correct 11101 ms 930656 KB Output is correct
65 Correct 11568 ms 930648 KB Output is correct

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 59604 KB Output is correct
2 Correct 23 ms 59628 KB Output is correct
3 Correct 24 ms 59724 KB Output is correct
4 Correct 22 ms 59632 KB Output is correct
5 Correct 22 ms 59604 KB Output is correct
6 Correct 23 ms 59596 KB Output is correct
7 Correct 26 ms 59668 KB Output is correct
8 Correct 23 ms 59568 KB Output is correct
9 Correct 22 ms 59604 KB Output is correct
10 Correct 22 ms 59604 KB Output is correct
11 Correct 22 ms 59616 KB Output is correct
12 Correct 22 ms 59604 KB Output is correct
13 Correct 23 ms 59616 KB Output is correct
14 Correct 24 ms 59580 KB Output is correct
15 Correct 23 ms 59604 KB Output is correct
16 Correct 26 ms 59604 KB Output is correct
17 Correct 23 ms 59604 KB Output is correct
18 Correct 25 ms 59604 KB Output is correct
19 Correct 27 ms 59656 KB Output is correct
20 Correct 25 ms 59696 KB Output is correct
21 Correct 22 ms 59624 KB Output is correct
22 Correct 22 ms 59604 KB Output is correct
23 Correct 22 ms 59616 KB Output is correct
24 Correct 23 ms 59648 KB Output is correct
25 Correct 26 ms 59600 KB Output is correct
26 Correct 30 ms 60004 KB Output is correct
27 Correct 146 ms 99368 KB Output is correct
28 Correct 163 ms 99760 KB Output is correct
29 Correct 634 ms 149288 KB Output is correct
30 Correct 620 ms 149956 KB Output is correct
31 Correct 552 ms 150104 KB Output is correct
32 Correct 529 ms 150208 KB Output is correct
33 Correct 619 ms 148056 KB Output is correct
34 Correct 617 ms 148808 KB Output is correct
35 Correct 492 ms 155080 KB Output is correct
36 Correct 602 ms 154364 KB Output is correct
37 Correct 657 ms 151356 KB Output is correct
38 Correct 566 ms 142428 KB Output is correct
39 Correct 683 ms 158084 KB Output is correct
40 Correct 550 ms 142696 KB Output is correct
41 Correct 575 ms 142368 KB Output is correct
42 Correct 556 ms 160760 KB Output is correct
43 Correct 465 ms 135516 KB Output is correct
44 Correct 472 ms 135132 KB Output is correct
45 Correct 354 ms 126460 KB Output is correct
46 Correct 351 ms 80272 KB Output is correct
47 Correct 3852 ms 269752 KB Output is correct
48 Correct 7190 ms 403280 KB Output is correct
49 Correct 9445 ms 530048 KB Output is correct
50 Correct 10026 ms 537408 KB Output is correct
51 Correct 9485 ms 544892 KB Output is correct
52 Correct 12906 ms 591824 KB Output is correct
53 Correct 12720 ms 593556 KB Output is correct
54 Correct 12893 ms 589444 KB Output is correct
55 Correct 12570 ms 586664 KB Output is correct
56 Correct 14040 ms 650408 KB Output is correct
57 Correct 15539 ms 719668 KB Output is correct
58 Correct 15837 ms 762724 KB Output is correct
59 Correct 16659 ms 817424 KB Output is correct
60 Correct 15197 ms 852004 KB Output is correct
61 Correct 15602 ms 882492 KB Output is correct
62 Correct 16847 ms 903700 KB Output is correct
63 Correct 16638 ms 913508 KB Output is correct
64 Correct 11101 ms 930656 KB Output is correct
65 Correct 11568 ms 930648 KB Output is correct
66 Correct 472 ms 135072 KB Output is correct
67 Correct 2537 ms 287548 KB Output is correct
68 Correct 9710 ms 937492 KB Output is correct
69 Correct 10037 ms 936628 KB Output is correct
70 Correct 9992 ms 978432 KB Output is correct
71 Execution timed out 18087 ms 273476 KB Time limit exceeded
72 Halted 0 ms 0 KB -