oj.uz

Submission #806811

# Submission time Handle Problem Language Result Execution time Memory
806811 2023-08-04T10:02:37 Z thimote75 Wild Boar (JOI18_wild_boar) C++14
12 / 100
 155 ms 174304 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);

        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:249: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]
  249 |         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 20 ms 59680 KB Output is correct
3 Correct 20 ms 59556 KB Output is correct
4 Correct 20 ms 59688 KB Output is correct
5 Correct 19 ms 59604 KB Output is correct
6 Correct 20 ms 59604 KB Output is correct
7 Correct 19 ms 59604 KB Output is correct
8 Correct 20 ms 59604 KB Output is correct
9 Correct 20 ms 59732 KB Output is correct
10 Correct 20 ms 59656 KB Output is correct
11 Correct 20 ms 59636 KB Output is correct
12 Correct 20 ms 59604 KB Output is correct
13 Correct 20 ms 59588 KB Output is correct
14 Correct 24 ms 59636 KB Output is correct
15 Correct 21 ms 59620 KB Output is correct
16 Correct 20 ms 59676 KB Output is correct
17 Correct 21 ms 59624 KB Output is correct
18 Correct 20 ms 59712 KB Output is correct
19 Correct 20 ms 59604 KB Output is correct
20 Correct 20 ms 59672 KB Output is correct
21 Correct 20 ms 59640 KB Output is correct
22 Correct 20 ms 59604 KB Output is correct
23 Correct 20 ms 59660 KB Output is correct
24 Correct 20 ms 59680 KB Output is correct
25 Correct 21 ms 59640 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 20 ms 59680 KB Output is correct
3 Correct 20 ms 59556 KB Output is correct
4 Correct 20 ms 59688 KB Output is correct
5 Correct 19 ms 59604 KB Output is correct
6 Correct 20 ms 59604 KB Output is correct
7 Correct 19 ms 59604 KB Output is correct
8 Correct 20 ms 59604 KB Output is correct
9 Correct 20 ms 59732 KB Output is correct
10 Correct 20 ms 59656 KB Output is correct
11 Correct 20 ms 59636 KB Output is correct
12 Correct 20 ms 59604 KB Output is correct
13 Correct 20 ms 59588 KB Output is correct
14 Correct 24 ms 59636 KB Output is correct
15 Correct 21 ms 59620 KB Output is correct
16 Correct 20 ms 59676 KB Output is correct
17 Correct 21 ms 59624 KB Output is correct
18 Correct 20 ms 59712 KB Output is correct
19 Correct 20 ms 59604 KB Output is correct
20 Correct 20 ms 59672 KB Output is correct
21 Correct 20 ms 59640 KB Output is correct
22 Correct 20 ms 59604 KB Output is correct
23 Correct 20 ms 59660 KB Output is correct
24 Correct 20 ms 59680 KB Output is correct
25 Correct 21 ms 59640 KB Output is correct
26 Correct 22 ms 59992 KB Output is correct
27 Runtime error 155 ms 174304 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 19 ms 59604 KB Output is correct
2 Correct 20 ms 59680 KB Output is correct
3 Correct 20 ms 59556 KB Output is correct
4 Correct 20 ms 59688 KB Output is correct
5 Correct 19 ms 59604 KB Output is correct
6 Correct 20 ms 59604 KB Output is correct
7 Correct 19 ms 59604 KB Output is correct
8 Correct 20 ms 59604 KB Output is correct
9 Correct 20 ms 59732 KB Output is correct
10 Correct 20 ms 59656 KB Output is correct
11 Correct 20 ms 59636 KB Output is correct
12 Correct 20 ms 59604 KB Output is correct
13 Correct 20 ms 59588 KB Output is correct
14 Correct 24 ms 59636 KB Output is correct
15 Correct 21 ms 59620 KB Output is correct
16 Correct 20 ms 59676 KB Output is correct
17 Correct 21 ms 59624 KB Output is correct
18 Correct 20 ms 59712 KB Output is correct
19 Correct 20 ms 59604 KB Output is correct
20 Correct 20 ms 59672 KB Output is correct
21 Correct 20 ms 59640 KB Output is correct
22 Correct 20 ms 59604 KB Output is correct
23 Correct 20 ms 59660 KB Output is correct
24 Correct 20 ms 59680 KB Output is correct
25 Correct 21 ms 59640 KB Output is correct
26 Correct 22 ms 59992 KB Output is correct
27 Runtime error 155 ms 174304 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 19 ms 59604 KB Output is correct
2 Correct 20 ms 59680 KB Output is correct
3 Correct 20 ms 59556 KB Output is correct
4 Correct 20 ms 59688 KB Output is correct
5 Correct 19 ms 59604 KB Output is correct
6 Correct 20 ms 59604 KB Output is correct
7 Correct 19 ms 59604 KB Output is correct
8 Correct 20 ms 59604 KB Output is correct
9 Correct 20 ms 59732 KB Output is correct
10 Correct 20 ms 59656 KB Output is correct
11 Correct 20 ms 59636 KB Output is correct
12 Correct 20 ms 59604 KB Output is correct
13 Correct 20 ms 59588 KB Output is correct
14 Correct 24 ms 59636 KB Output is correct
15 Correct 21 ms 59620 KB Output is correct
16 Correct 20 ms 59676 KB Output is correct
17 Correct 21 ms 59624 KB Output is correct
18 Correct 20 ms 59712 KB Output is correct
19 Correct 20 ms 59604 KB Output is correct
20 Correct 20 ms 59672 KB Output is correct
21 Correct 20 ms 59640 KB Output is correct
22 Correct 20 ms 59604 KB Output is correct
23 Correct 20 ms 59660 KB Output is correct
24 Correct 20 ms 59680 KB Output is correct
25 Correct 21 ms 59640 KB Output is correct
26 Correct 22 ms 59992 KB Output is correct
27 Runtime error 155 ms 174304 KB Execution killed with signal 11
28 Halted 0 ms 0 KB -