oj.uz

Submission #806796

# Submission time Handle Problem Language Result Execution time Memory
806796 2023-08-04T09:59:48 Z thimote75 Wild Boar (JOI18_wild_boar) C++14
12 / 100
 124 ms 128884 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 () {
    assert(buffer_pos < 5000);
    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);
    }
    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]] );
        
        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:247: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]
  247 |         for (int i = 1; i < queries.size(); i ++)
      |                         ~~^~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 59604 KB Output is correct
2 Correct 21 ms 59604 KB Output is correct
3 Correct 19 ms 59616 KB Output is correct
4 Correct 20 ms 59672 KB Output is correct
5 Correct 20 ms 59668 KB Output is correct
6 Correct 22 ms 59628 KB Output is correct
7 Correct 20 ms 59648 KB Output is correct
8 Correct 20 ms 59636 KB Output is correct
9 Correct 22 ms 59692 KB Output is correct
10 Correct 24 ms 59608 KB Output is correct
11 Correct 20 ms 59612 KB Output is correct
12 Correct 20 ms 59644 KB Output is correct
13 Correct 20 ms 59704 KB Output is correct
14 Correct 20 ms 59676 KB Output is correct
15 Correct 20 ms 59604 KB Output is correct
16 Correct 21 ms 59600 KB Output is correct
17 Correct 21 ms 59624 KB Output is correct
18 Correct 20 ms 59672 KB Output is correct
19 Correct 20 ms 59604 KB Output is correct
20 Correct 20 ms 59720 KB Output is correct
21 Correct 20 ms 59632 KB Output is correct
22 Correct 23 ms 59652 KB Output is correct
23 Correct 25 ms 59672 KB Output is correct
24 Correct 22 ms 59604 KB Output is correct
25 Correct 23 ms 59576 KB Output is correct

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 59604 KB Output is correct
2 Correct 21 ms 59604 KB Output is correct
3 Correct 19 ms 59616 KB Output is correct
4 Correct 20 ms 59672 KB Output is correct
5 Correct 20 ms 59668 KB Output is correct
6 Correct 22 ms 59628 KB Output is correct
7 Correct 20 ms 59648 KB Output is correct
8 Correct 20 ms 59636 KB Output is correct
9 Correct 22 ms 59692 KB Output is correct
10 Correct 24 ms 59608 KB Output is correct
11 Correct 20 ms 59612 KB Output is correct
12 Correct 20 ms 59644 KB Output is correct
13 Correct 20 ms 59704 KB Output is correct
14 Correct 20 ms 59676 KB Output is correct
15 Correct 20 ms 59604 KB Output is correct
16 Correct 21 ms 59600 KB Output is correct
17 Correct 21 ms 59624 KB Output is correct
18 Correct 20 ms 59672 KB Output is correct
19 Correct 20 ms 59604 KB Output is correct
20 Correct 20 ms 59720 KB Output is correct
21 Correct 20 ms 59632 KB Output is correct
22 Correct 23 ms 59652 KB Output is correct
23 Correct 25 ms 59672 KB Output is correct
24 Correct 22 ms 59604 KB Output is correct
25 Correct 23 ms 59576 KB Output is correct
26 Correct 24 ms 59988 KB Output is correct
27 Runtime error 124 ms 128884 KB Execution killed with signal 6
28 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 59604 KB Output is correct
2 Correct 21 ms 59604 KB Output is correct
3 Correct 19 ms 59616 KB Output is correct
4 Correct 20 ms 59672 KB Output is correct
5 Correct 20 ms 59668 KB Output is correct
6 Correct 22 ms 59628 KB Output is correct
7 Correct 20 ms 59648 KB Output is correct
8 Correct 20 ms 59636 KB Output is correct
9 Correct 22 ms 59692 KB Output is correct
10 Correct 24 ms 59608 KB Output is correct
11 Correct 20 ms 59612 KB Output is correct
12 Correct 20 ms 59644 KB Output is correct
13 Correct 20 ms 59704 KB Output is correct
14 Correct 20 ms 59676 KB Output is correct
15 Correct 20 ms 59604 KB Output is correct
16 Correct 21 ms 59600 KB Output is correct
17 Correct 21 ms 59624 KB Output is correct
18 Correct 20 ms 59672 KB Output is correct
19 Correct 20 ms 59604 KB Output is correct
20 Correct 20 ms 59720 KB Output is correct
21 Correct 20 ms 59632 KB Output is correct
22 Correct 23 ms 59652 KB Output is correct
23 Correct 25 ms 59672 KB Output is correct
24 Correct 22 ms 59604 KB Output is correct
25 Correct 23 ms 59576 KB Output is correct
26 Correct 24 ms 59988 KB Output is correct
27 Runtime error 124 ms 128884 KB Execution killed with signal 6
28 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 59604 KB Output is correct
2 Correct 21 ms 59604 KB Output is correct
3 Correct 19 ms 59616 KB Output is correct
4 Correct 20 ms 59672 KB Output is correct
5 Correct 20 ms 59668 KB Output is correct
6 Correct 22 ms 59628 KB Output is correct
7 Correct 20 ms 59648 KB Output is correct
8 Correct 20 ms 59636 KB Output is correct
9 Correct 22 ms 59692 KB Output is correct
10 Correct 24 ms 59608 KB Output is correct
11 Correct 20 ms 59612 KB Output is correct
12 Correct 20 ms 59644 KB Output is correct
13 Correct 20 ms 59704 KB Output is correct
14 Correct 20 ms 59676 KB Output is correct
15 Correct 20 ms 59604 KB Output is correct
16 Correct 21 ms 59600 KB Output is correct
17 Correct 21 ms 59624 KB Output is correct
18 Correct 20 ms 59672 KB Output is correct
19 Correct 20 ms 59604 KB Output is correct
20 Correct 20 ms 59720 KB Output is correct
21 Correct 20 ms 59632 KB Output is correct
22 Correct 23 ms 59652 KB Output is correct
23 Correct 25 ms 59672 KB Output is correct
24 Correct 22 ms 59604 KB Output is correct
25 Correct 23 ms 59576 KB Output is correct
26 Correct 24 ms 59988 KB Output is correct
27 Runtime error 124 ms 128884 KB Execution killed with signal 6
28 Halted 0 ms 0 KB -