oj.uz

답안 #806805

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
806805 2023-08-04T10:01:04 Z thimote75 Wild Boar (JOI18_wild_boar) C++14
12 / 100
 153 ms 174228 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]] );
        
        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

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 59556 KB Output is correct
2 Correct 24 ms 59668 KB Output is correct
3 Correct 20 ms 59588 KB Output is correct
4 Correct 24 ms 59660 KB Output is correct
5 Correct 20 ms 59604 KB Output is correct
6 Correct 20 ms 59576 KB Output is correct
7 Correct 20 ms 59604 KB Output is correct
8 Correct 21 ms 59644 KB Output is correct
9 Correct 21 ms 59644 KB Output is correct
10 Correct 20 ms 59596 KB Output is correct
11 Correct 19 ms 59604 KB Output is correct
12 Correct 21 ms 59604 KB Output is correct
13 Correct 20 ms 59604 KB Output is correct
14 Correct 20 ms 59604 KB Output is correct
15 Correct 21 ms 59660 KB Output is correct
16 Correct 21 ms 59664 KB Output is correct
17 Correct 20 ms 59600 KB Output is correct
18 Correct 20 ms 59636 KB Output is correct
19 Correct 20 ms 59724 KB Output is correct
20 Correct 20 ms 59716 KB Output is correct
21 Correct 21 ms 59564 KB Output is correct
22 Correct 21 ms 59604 KB Output is correct
23 Correct 21 ms 59604 KB Output is correct
24 Correct 21 ms 59636 KB Output is correct
25 Correct 20 ms 59616 KB Output is correct

Subtask #2
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 59556 KB Output is correct
2 Correct 24 ms 59668 KB Output is correct
3 Correct 20 ms 59588 KB Output is correct
4 Correct 24 ms 59660 KB Output is correct
5 Correct 20 ms 59604 KB Output is correct
6 Correct 20 ms 59576 KB Output is correct
7 Correct 20 ms 59604 KB Output is correct
8 Correct 21 ms 59644 KB Output is correct
9 Correct 21 ms 59644 KB Output is correct
10 Correct 20 ms 59596 KB Output is correct
11 Correct 19 ms 59604 KB Output is correct
12 Correct 21 ms 59604 KB Output is correct
13 Correct 20 ms 59604 KB Output is correct
14 Correct 20 ms 59604 KB Output is correct
15 Correct 21 ms 59660 KB Output is correct
16 Correct 21 ms 59664 KB Output is correct
17 Correct 20 ms 59600 KB Output is correct
18 Correct 20 ms 59636 KB Output is correct
19 Correct 20 ms 59724 KB Output is correct
20 Correct 20 ms 59716 KB Output is correct
21 Correct 21 ms 59564 KB Output is correct
22 Correct 21 ms 59604 KB Output is correct
23 Correct 21 ms 59604 KB Output is correct
24 Correct 21 ms 59636 KB Output is correct
25 Correct 20 ms 59616 KB Output is correct
26 Correct 23 ms 59996 KB Output is correct
27 Runtime error 153 ms 174228 KB Execution killed with signal 11
28 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 59556 KB Output is correct
2 Correct 24 ms 59668 KB Output is correct
3 Correct 20 ms 59588 KB Output is correct
4 Correct 24 ms 59660 KB Output is correct
5 Correct 20 ms 59604 KB Output is correct
6 Correct 20 ms 59576 KB Output is correct
7 Correct 20 ms 59604 KB Output is correct
8 Correct 21 ms 59644 KB Output is correct
9 Correct 21 ms 59644 KB Output is correct
10 Correct 20 ms 59596 KB Output is correct
11 Correct 19 ms 59604 KB Output is correct
12 Correct 21 ms 59604 KB Output is correct
13 Correct 20 ms 59604 KB Output is correct
14 Correct 20 ms 59604 KB Output is correct
15 Correct 21 ms 59660 KB Output is correct
16 Correct 21 ms 59664 KB Output is correct
17 Correct 20 ms 59600 KB Output is correct
18 Correct 20 ms 59636 KB Output is correct
19 Correct 20 ms 59724 KB Output is correct
20 Correct 20 ms 59716 KB Output is correct
21 Correct 21 ms 59564 KB Output is correct
22 Correct 21 ms 59604 KB Output is correct
23 Correct 21 ms 59604 KB Output is correct
24 Correct 21 ms 59636 KB Output is correct
25 Correct 20 ms 59616 KB Output is correct
26 Correct 23 ms 59996 KB Output is correct
27 Runtime error 153 ms 174228 KB Execution killed with signal 11
28 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 59556 KB Output is correct
2 Correct 24 ms 59668 KB Output is correct
3 Correct 20 ms 59588 KB Output is correct
4 Correct 24 ms 59660 KB Output is correct
5 Correct 20 ms 59604 KB Output is correct
6 Correct 20 ms 59576 KB Output is correct
7 Correct 20 ms 59604 KB Output is correct
8 Correct 21 ms 59644 KB Output is correct
9 Correct 21 ms 59644 KB Output is correct
10 Correct 20 ms 59596 KB Output is correct
11 Correct 19 ms 59604 KB Output is correct
12 Correct 21 ms 59604 KB Output is correct
13 Correct 20 ms 59604 KB Output is correct
14 Correct 20 ms 59604 KB Output is correct
15 Correct 21 ms 59660 KB Output is correct
16 Correct 21 ms 59664 KB Output is correct
17 Correct 20 ms 59600 KB Output is correct
18 Correct 20 ms 59636 KB Output is correct
19 Correct 20 ms 59724 KB Output is correct
20 Correct 20 ms 59716 KB Output is correct
21 Correct 21 ms 59564 KB Output is correct
22 Correct 21 ms 59604 KB Output is correct
23 Correct 21 ms 59604 KB Output is correct
24 Correct 21 ms 59636 KB Output is correct
25 Correct 20 ms 59616 KB Output is correct
26 Correct 23 ms 59996 KB Output is correct
27 Runtime error 153 ms 174228 KB Execution killed with signal 11
28 Halted 0 ms 0 KB -