oj.uz

Submission #806793

# Submission time Handle Problem Language Result Execution time Memory
806793 2023-08-04T09:58:23 Z thimote75 Wild Boar (JOI18_wild_boar) C++14
12 / 100
 144 ms 174500 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 () {
    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:246: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]
  246 |         for (int i = 1; i < queries.size(); i ++)
      |                         ~~^~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 59604 KB Output is correct
2 Correct 21 ms 59616 KB Output is correct
3 Correct 20 ms 59664 KB Output is correct
4 Correct 22 ms 59620 KB Output is correct
5 Correct 22 ms 59668 KB Output is correct
6 Correct 21 ms 59624 KB Output is correct
7 Correct 21 ms 59684 KB Output is correct
8 Correct 21 ms 59644 KB Output is correct
9 Correct 22 ms 59604 KB Output is correct
10 Correct 21 ms 59736 KB Output is correct
11 Correct 21 ms 59700 KB Output is correct
12 Correct 22 ms 59612 KB Output is correct
13 Correct 22 ms 59664 KB Output is correct
14 Correct 21 ms 59600 KB Output is correct
15 Correct 22 ms 59612 KB Output is correct
16 Correct 20 ms 59684 KB Output is correct
17 Correct 20 ms 59724 KB Output is correct
18 Correct 20 ms 59704 KB Output is correct
19 Correct 21 ms 59616 KB Output is correct
20 Correct 21 ms 59604 KB Output is correct
21 Correct 20 ms 59652 KB Output is correct
22 Correct 21 ms 59656 KB Output is correct
23 Correct 21 ms 59616 KB Output is correct
24 Correct 21 ms 59604 KB Output is correct
25 Correct 21 ms 59560 KB Output is correct

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 59604 KB Output is correct
2 Correct 21 ms 59616 KB Output is correct
3 Correct 20 ms 59664 KB Output is correct
4 Correct 22 ms 59620 KB Output is correct
5 Correct 22 ms 59668 KB Output is correct
6 Correct 21 ms 59624 KB Output is correct
7 Correct 21 ms 59684 KB Output is correct
8 Correct 21 ms 59644 KB Output is correct
9 Correct 22 ms 59604 KB Output is correct
10 Correct 21 ms 59736 KB Output is correct
11 Correct 21 ms 59700 KB Output is correct
12 Correct 22 ms 59612 KB Output is correct
13 Correct 22 ms 59664 KB Output is correct
14 Correct 21 ms 59600 KB Output is correct
15 Correct 22 ms 59612 KB Output is correct
16 Correct 20 ms 59684 KB Output is correct
17 Correct 20 ms 59724 KB Output is correct
18 Correct 20 ms 59704 KB Output is correct
19 Correct 21 ms 59616 KB Output is correct
20 Correct 21 ms 59604 KB Output is correct
21 Correct 20 ms 59652 KB Output is correct
22 Correct 21 ms 59656 KB Output is correct
23 Correct 21 ms 59616 KB Output is correct
24 Correct 21 ms 59604 KB Output is correct
25 Correct 21 ms 59560 KB Output is correct
26 Correct 22 ms 60000 KB Output is correct
27 Runtime error 144 ms 174500 KB Execution killed with signal 11
28 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 59604 KB Output is correct
2 Correct 21 ms 59616 KB Output is correct
3 Correct 20 ms 59664 KB Output is correct
4 Correct 22 ms 59620 KB Output is correct
5 Correct 22 ms 59668 KB Output is correct
6 Correct 21 ms 59624 KB Output is correct
7 Correct 21 ms 59684 KB Output is correct
8 Correct 21 ms 59644 KB Output is correct
9 Correct 22 ms 59604 KB Output is correct
10 Correct 21 ms 59736 KB Output is correct
11 Correct 21 ms 59700 KB Output is correct
12 Correct 22 ms 59612 KB Output is correct
13 Correct 22 ms 59664 KB Output is correct
14 Correct 21 ms 59600 KB Output is correct
15 Correct 22 ms 59612 KB Output is correct
16 Correct 20 ms 59684 KB Output is correct
17 Correct 20 ms 59724 KB Output is correct
18 Correct 20 ms 59704 KB Output is correct
19 Correct 21 ms 59616 KB Output is correct
20 Correct 21 ms 59604 KB Output is correct
21 Correct 20 ms 59652 KB Output is correct
22 Correct 21 ms 59656 KB Output is correct
23 Correct 21 ms 59616 KB Output is correct
24 Correct 21 ms 59604 KB Output is correct
25 Correct 21 ms 59560 KB Output is correct
26 Correct 22 ms 60000 KB Output is correct
27 Runtime error 144 ms 174500 KB Execution killed with signal 11
28 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 59604 KB Output is correct
2 Correct 21 ms 59616 KB Output is correct
3 Correct 20 ms 59664 KB Output is correct
4 Correct 22 ms 59620 KB Output is correct
5 Correct 22 ms 59668 KB Output is correct
6 Correct 21 ms 59624 KB Output is correct
7 Correct 21 ms 59684 KB Output is correct
8 Correct 21 ms 59644 KB Output is correct
9 Correct 22 ms 59604 KB Output is correct
10 Correct 21 ms 59736 KB Output is correct
11 Correct 21 ms 59700 KB Output is correct
12 Correct 22 ms 59612 KB Output is correct
13 Correct 22 ms 59664 KB Output is correct
14 Correct 21 ms 59600 KB Output is correct
15 Correct 22 ms 59612 KB Output is correct
16 Correct 20 ms 59684 KB Output is correct
17 Correct 20 ms 59724 KB Output is correct
18 Correct 20 ms 59704 KB Output is correct
19 Correct 21 ms 59616 KB Output is correct
20 Correct 21 ms 59604 KB Output is correct
21 Correct 20 ms 59652 KB Output is correct
22 Correct 21 ms 59656 KB Output is correct
23 Correct 21 ms 59616 KB Output is correct
24 Correct 21 ms 59604 KB Output is correct
25 Correct 21 ms 59560 KB Output is correct
26 Correct 22 ms 60000 KB Output is correct
27 Runtime error 144 ms 174500 KB Execution killed with signal 11
28 Halted 0 ms 0 KB -