oj.uz

Submission #806767

# Submission time Handle Problem Language Result Execution time Memory
806767 2023-08-04T09:41:46 Z thimote75 Wild Boar (JOI18_wild_boar) C++14
12 / 100
 446 ms 28772 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 = 0;
    void clear () {
        stage ++;
    }
    void check (int node) {
        if (vp[node] != stage) {
            vp[node] = stage;
            lp[node] = dp[node];
        }
    } 
    int get (int x) {
        check(x);
        return dp[x] - lp[x];
    }
    void insert (int x) {
        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;
}

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 9 ms 20564 KB Output is correct
2 Correct 9 ms 20564 KB Output is correct
3 Correct 8 ms 20548 KB Output is correct
4 Correct 8 ms 20564 KB Output is correct
5 Correct 10 ms 20564 KB Output is correct
6 Correct 8 ms 20644 KB Output is correct
7 Correct 8 ms 20680 KB Output is correct
8 Correct 8 ms 20632 KB Output is correct
9 Correct 8 ms 20692 KB Output is correct
10 Correct 8 ms 20588 KB Output is correct
11 Correct 8 ms 20692 KB Output is correct
12 Correct 10 ms 20692 KB Output is correct
13 Correct 8 ms 20692 KB Output is correct
14 Correct 8 ms 20680 KB Output is correct
15 Correct 8 ms 20732 KB Output is correct
16 Correct 8 ms 20692 KB Output is correct
17 Correct 8 ms 20692 KB Output is correct
18 Correct 8 ms 20724 KB Output is correct
19 Correct 10 ms 20692 KB Output is correct
20 Correct 8 ms 20692 KB Output is correct
21 Correct 8 ms 20564 KB Output is correct
22 Correct 11 ms 20564 KB Output is correct
23 Correct 8 ms 20552 KB Output is correct
24 Correct 10 ms 20564 KB Output is correct
25 Correct 8 ms 20608 KB Output is correct

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 20564 KB Output is correct
2 Correct 9 ms 20564 KB Output is correct
3 Correct 8 ms 20548 KB Output is correct
4 Correct 8 ms 20564 KB Output is correct
5 Correct 10 ms 20564 KB Output is correct
6 Correct 8 ms 20644 KB Output is correct
7 Correct 8 ms 20680 KB Output is correct
8 Correct 8 ms 20632 KB Output is correct
9 Correct 8 ms 20692 KB Output is correct
10 Correct 8 ms 20588 KB Output is correct
11 Correct 8 ms 20692 KB Output is correct
12 Correct 10 ms 20692 KB Output is correct
13 Correct 8 ms 20692 KB Output is correct
14 Correct 8 ms 20680 KB Output is correct
15 Correct 8 ms 20732 KB Output is correct
16 Correct 8 ms 20692 KB Output is correct
17 Correct 8 ms 20692 KB Output is correct
18 Correct 8 ms 20724 KB Output is correct
19 Correct 10 ms 20692 KB Output is correct
20 Correct 8 ms 20692 KB Output is correct
21 Correct 8 ms 20564 KB Output is correct
22 Correct 11 ms 20564 KB Output is correct
23 Correct 8 ms 20552 KB Output is correct
24 Correct 10 ms 20564 KB Output is correct
25 Correct 8 ms 20608 KB Output is correct
26 Correct 11 ms 21076 KB Output is correct
27 Correct 28 ms 25420 KB Output is correct
28 Correct 26 ms 25456 KB Output is correct
29 Incorrect 446 ms 28772 KB Output isn't correct
30 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 20564 KB Output is correct
2 Correct 9 ms 20564 KB Output is correct
3 Correct 8 ms 20548 KB Output is correct
4 Correct 8 ms 20564 KB Output is correct
5 Correct 10 ms 20564 KB Output is correct
6 Correct 8 ms 20644 KB Output is correct
7 Correct 8 ms 20680 KB Output is correct
8 Correct 8 ms 20632 KB Output is correct
9 Correct 8 ms 20692 KB Output is correct
10 Correct 8 ms 20588 KB Output is correct
11 Correct 8 ms 20692 KB Output is correct
12 Correct 10 ms 20692 KB Output is correct
13 Correct 8 ms 20692 KB Output is correct
14 Correct 8 ms 20680 KB Output is correct
15 Correct 8 ms 20732 KB Output is correct
16 Correct 8 ms 20692 KB Output is correct
17 Correct 8 ms 20692 KB Output is correct
18 Correct 8 ms 20724 KB Output is correct
19 Correct 10 ms 20692 KB Output is correct
20 Correct 8 ms 20692 KB Output is correct
21 Correct 8 ms 20564 KB Output is correct
22 Correct 11 ms 20564 KB Output is correct
23 Correct 8 ms 20552 KB Output is correct
24 Correct 10 ms 20564 KB Output is correct
25 Correct 8 ms 20608 KB Output is correct
26 Correct 11 ms 21076 KB Output is correct
27 Correct 28 ms 25420 KB Output is correct
28 Correct 26 ms 25456 KB Output is correct
29 Incorrect 446 ms 28772 KB Output isn't correct
30 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 20564 KB Output is correct
2 Correct 9 ms 20564 KB Output is correct
3 Correct 8 ms 20548 KB Output is correct
4 Correct 8 ms 20564 KB Output is correct
5 Correct 10 ms 20564 KB Output is correct
6 Correct 8 ms 20644 KB Output is correct
7 Correct 8 ms 20680 KB Output is correct
8 Correct 8 ms 20632 KB Output is correct
9 Correct 8 ms 20692 KB Output is correct
10 Correct 8 ms 20588 KB Output is correct
11 Correct 8 ms 20692 KB Output is correct
12 Correct 10 ms 20692 KB Output is correct
13 Correct 8 ms 20692 KB Output is correct
14 Correct 8 ms 20680 KB Output is correct
15 Correct 8 ms 20732 KB Output is correct
16 Correct 8 ms 20692 KB Output is correct
17 Correct 8 ms 20692 KB Output is correct
18 Correct 8 ms 20724 KB Output is correct
19 Correct 10 ms 20692 KB Output is correct
20 Correct 8 ms 20692 KB Output is correct
21 Correct 8 ms 20564 KB Output is correct
22 Correct 11 ms 20564 KB Output is correct
23 Correct 8 ms 20552 KB Output is correct
24 Correct 10 ms 20564 KB Output is correct
25 Correct 8 ms 20608 KB Output is correct
26 Correct 11 ms 21076 KB Output is correct
27 Correct 28 ms 25420 KB Output is correct
28 Correct 26 ms 25456 KB Output is correct
29 Incorrect 446 ms 28772 KB Output isn't correct
30 Halted 0 ms 0 KB -