oj.uz

Submission #806769

# Submission time Handle Problem Language Result Execution time Memory
806769 2023-08-04T09:43:57 Z thimote75 Wild Boar (JOI18_wild_boar) C++14
62 / 100
 18000 ms 886492 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;
}

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 22 ms 59864 KB Output is correct
2 Correct 23 ms 59928 KB Output is correct
3 Correct 21 ms 59956 KB Output is correct
4 Correct 22 ms 59936 KB Output is correct
5 Correct 27 ms 59916 KB Output is correct
6 Correct 22 ms 60000 KB Output is correct
7 Correct 22 ms 59988 KB Output is correct
8 Correct 23 ms 59988 KB Output is correct
9 Correct 23 ms 59904 KB Output is correct
10 Correct 22 ms 59936 KB Output is correct
11 Correct 23 ms 59916 KB Output is correct
12 Correct 22 ms 59988 KB Output is correct
13 Correct 23 ms 59996 KB Output is correct
14 Correct 22 ms 59948 KB Output is correct
15 Correct 23 ms 59944 KB Output is correct
16 Correct 24 ms 59988 KB Output is correct
17 Correct 24 ms 59932 KB Output is correct
18 Correct 24 ms 59952 KB Output is correct
19 Correct 23 ms 59920 KB Output is correct
20 Correct 26 ms 59988 KB Output is correct
21 Correct 26 ms 59956 KB Output is correct
22 Correct 23 ms 59904 KB Output is correct
23 Correct 26 ms 60020 KB Output is correct
24 Correct 23 ms 59968 KB Output is correct
25 Correct 24 ms 59912 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 59864 KB Output is correct
2 Correct 23 ms 59928 KB Output is correct
3 Correct 21 ms 59956 KB Output is correct
4 Correct 22 ms 59936 KB Output is correct
5 Correct 27 ms 59916 KB Output is correct
6 Correct 22 ms 60000 KB Output is correct
7 Correct 22 ms 59988 KB Output is correct
8 Correct 23 ms 59988 KB Output is correct
9 Correct 23 ms 59904 KB Output is correct
10 Correct 22 ms 59936 KB Output is correct
11 Correct 23 ms 59916 KB Output is correct
12 Correct 22 ms 59988 KB Output is correct
13 Correct 23 ms 59996 KB Output is correct
14 Correct 22 ms 59948 KB Output is correct
15 Correct 23 ms 59944 KB Output is correct
16 Correct 24 ms 59988 KB Output is correct
17 Correct 24 ms 59932 KB Output is correct
18 Correct 24 ms 59952 KB Output is correct
19 Correct 23 ms 59920 KB Output is correct
20 Correct 26 ms 59988 KB Output is correct
21 Correct 26 ms 59956 KB Output is correct
22 Correct 23 ms 59904 KB Output is correct
23 Correct 26 ms 60020 KB Output is correct
24 Correct 23 ms 59968 KB Output is correct
25 Correct 24 ms 59912 KB Output is correct
26 Correct 26 ms 60232 KB Output is correct
27 Correct 41 ms 63672 KB Output is correct
28 Correct 42 ms 63660 KB Output is correct
29 Correct 486 ms 66856 KB Output is correct
30 Correct 500 ms 66664 KB Output is correct
31 Correct 381 ms 66872 KB Output is correct
32 Correct 382 ms 67108 KB Output is correct
33 Correct 464 ms 72392 KB Output is correct
34 Correct 487 ms 72656 KB Output is correct
35 Correct 430 ms 71692 KB Output is correct
36 Correct 411 ms 71104 KB Output is correct
37 Correct 487 ms 72960 KB Output is correct
38 Correct 496 ms 77404 KB Output is correct
39 Correct 440 ms 74796 KB Output is correct
40 Correct 366 ms 77392 KB Output is correct
41 Correct 342 ms 77388 KB Output is correct
42 Correct 470 ms 77460 KB Output is correct
43 Correct 310 ms 80784 KB Output is correct
44 Correct 331 ms 80592 KB Output is correct
45 Correct 219 ms 82096 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 59864 KB Output is correct
2 Correct 23 ms 59928 KB Output is correct
3 Correct 21 ms 59956 KB Output is correct
4 Correct 22 ms 59936 KB Output is correct
5 Correct 27 ms 59916 KB Output is correct
6 Correct 22 ms 60000 KB Output is correct
7 Correct 22 ms 59988 KB Output is correct
8 Correct 23 ms 59988 KB Output is correct
9 Correct 23 ms 59904 KB Output is correct
10 Correct 22 ms 59936 KB Output is correct
11 Correct 23 ms 59916 KB Output is correct
12 Correct 22 ms 59988 KB Output is correct
13 Correct 23 ms 59996 KB Output is correct
14 Correct 22 ms 59948 KB Output is correct
15 Correct 23 ms 59944 KB Output is correct
16 Correct 24 ms 59988 KB Output is correct
17 Correct 24 ms 59932 KB Output is correct
18 Correct 24 ms 59952 KB Output is correct
19 Correct 23 ms 59920 KB Output is correct
20 Correct 26 ms 59988 KB Output is correct
21 Correct 26 ms 59956 KB Output is correct
22 Correct 23 ms 59904 KB Output is correct
23 Correct 26 ms 60020 KB Output is correct
24 Correct 23 ms 59968 KB Output is correct
25 Correct 24 ms 59912 KB Output is correct
26 Correct 26 ms 60232 KB Output is correct
27 Correct 41 ms 63672 KB Output is correct
28 Correct 42 ms 63660 KB Output is correct
29 Correct 486 ms 66856 KB Output is correct
30 Correct 500 ms 66664 KB Output is correct
31 Correct 381 ms 66872 KB Output is correct
32 Correct 382 ms 67108 KB Output is correct
33 Correct 464 ms 72392 KB Output is correct
34 Correct 487 ms 72656 KB Output is correct
35 Correct 430 ms 71692 KB Output is correct
36 Correct 411 ms 71104 KB Output is correct
37 Correct 487 ms 72960 KB Output is correct
38 Correct 496 ms 77404 KB Output is correct
39 Correct 440 ms 74796 KB Output is correct
40 Correct 366 ms 77392 KB Output is correct
41 Correct 342 ms 77388 KB Output is correct
42 Correct 470 ms 77460 KB Output is correct
43 Correct 310 ms 80784 KB Output is correct
44 Correct 331 ms 80592 KB Output is correct
45 Correct 219 ms 82096 KB Output is correct
46 Correct 337 ms 80492 KB Output is correct
47 Correct 3615 ms 186756 KB Output is correct
48 Correct 6253 ms 319896 KB Output is correct
49 Correct 8927 ms 446584 KB Output is correct
50 Correct 9175 ms 453820 KB Output is correct
51 Correct 8629 ms 461408 KB Output is correct
52 Correct 11503 ms 516416 KB Output is correct
53 Correct 11766 ms 517924 KB Output is correct
54 Correct 11256 ms 514264 KB Output is correct
55 Correct 11536 ms 512424 KB Output is correct
56 Correct 13017 ms 578880 KB Output is correct
57 Correct 14764 ms 649416 KB Output is correct
58 Correct 15565 ms 695844 KB Output is correct
59 Correct 16233 ms 753488 KB Output is correct
60 Correct 16722 ms 791716 KB Output is correct
61 Correct 17255 ms 825664 KB Output is correct
62 Correct 16855 ms 850316 KB Output is correct
63 Correct 16477 ms 863744 KB Output is correct
64 Correct 10183 ms 886460 KB Output is correct
65 Correct 10335 ms 886492 KB Output is correct

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 59864 KB Output is correct
2 Correct 23 ms 59928 KB Output is correct
3 Correct 21 ms 59956 KB Output is correct
4 Correct 22 ms 59936 KB Output is correct
5 Correct 27 ms 59916 KB Output is correct
6 Correct 22 ms 60000 KB Output is correct
7 Correct 22 ms 59988 KB Output is correct
8 Correct 23 ms 59988 KB Output is correct
9 Correct 23 ms 59904 KB Output is correct
10 Correct 22 ms 59936 KB Output is correct
11 Correct 23 ms 59916 KB Output is correct
12 Correct 22 ms 59988 KB Output is correct
13 Correct 23 ms 59996 KB Output is correct
14 Correct 22 ms 59948 KB Output is correct
15 Correct 23 ms 59944 KB Output is correct
16 Correct 24 ms 59988 KB Output is correct
17 Correct 24 ms 59932 KB Output is correct
18 Correct 24 ms 59952 KB Output is correct
19 Correct 23 ms 59920 KB Output is correct
20 Correct 26 ms 59988 KB Output is correct
21 Correct 26 ms 59956 KB Output is correct
22 Correct 23 ms 59904 KB Output is correct
23 Correct 26 ms 60020 KB Output is correct
24 Correct 23 ms 59968 KB Output is correct
25 Correct 24 ms 59912 KB Output is correct
26 Correct 26 ms 60232 KB Output is correct
27 Correct 41 ms 63672 KB Output is correct
28 Correct 42 ms 63660 KB Output is correct
29 Correct 486 ms 66856 KB Output is correct
30 Correct 500 ms 66664 KB Output is correct
31 Correct 381 ms 66872 KB Output is correct
32 Correct 382 ms 67108 KB Output is correct
33 Correct 464 ms 72392 KB Output is correct
34 Correct 487 ms 72656 KB Output is correct
35 Correct 430 ms 71692 KB Output is correct
36 Correct 411 ms 71104 KB Output is correct
37 Correct 487 ms 72960 KB Output is correct
38 Correct 496 ms 77404 KB Output is correct
39 Correct 440 ms 74796 KB Output is correct
40 Correct 366 ms 77392 KB Output is correct
41 Correct 342 ms 77388 KB Output is correct
42 Correct 470 ms 77460 KB Output is correct
43 Correct 310 ms 80784 KB Output is correct
44 Correct 331 ms 80592 KB Output is correct
45 Correct 219 ms 82096 KB Output is correct
46 Correct 337 ms 80492 KB Output is correct
47 Correct 3615 ms 186756 KB Output is correct
48 Correct 6253 ms 319896 KB Output is correct
49 Correct 8927 ms 446584 KB Output is correct
50 Correct 9175 ms 453820 KB Output is correct
51 Correct 8629 ms 461408 KB Output is correct
52 Correct 11503 ms 516416 KB Output is correct
53 Correct 11766 ms 517924 KB Output is correct
54 Correct 11256 ms 514264 KB Output is correct
55 Correct 11536 ms 512424 KB Output is correct
56 Correct 13017 ms 578880 KB Output is correct
57 Correct 14764 ms 649416 KB Output is correct
58 Correct 15565 ms 695844 KB Output is correct
59 Correct 16233 ms 753488 KB Output is correct
60 Correct 16722 ms 791716 KB Output is correct
61 Correct 17255 ms 825664 KB Output is correct
62 Correct 16855 ms 850316 KB Output is correct
63 Correct 16477 ms 863744 KB Output is correct
64 Correct 10183 ms 886460 KB Output is correct
65 Correct 10335 ms 886492 KB Output is correct
66 Execution timed out 18066 ms 61260 KB Time limit exceeded
67 Halted 0 ms 0 KB -