oj.uz

Submission #967206

# Submission time Handle Problem Language Result Execution time Memory
967206 2024-04-21T13:49:08 Z socpite Bridges (APIO19_bridges) C++14
0 / 100
 3000 ms 14304 KB 
#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e5+5;
const int blsz = 10000;

int n, m, q;

int U[maxn], V[maxn], W[maxn];

int Wnew[maxn];

int T[maxn], id[maxn], val[maxn], ans[maxn];
bool chk[maxn];

int up[maxn], vis[maxn];

vector<int> g[maxn];

int dfs(int x, int pos){
    int res = -up[x];
    vis[x] = pos;
    for(auto v: g[x]){
        if(vis[v] == pos)continue;
        res += dfs(v, pos);
    }
    return res;
}

int Find(int x){
    return up[x] < 0 ? x : up[x] = Find(up[x]);
}

void Union(int a, int b){
    a = Find(a);
    b = Find(b);
    if(a == b)return;
    up[a] += up[b];
    up[b] = a;
}

struct cmp{
    bool operator()(const int &a, const int &b)const {
        return make_pair(W[a], a) > make_pair(W[b], b);
    }
};

void solve_query(int l, int pos, vector<int> &changed){
    for(auto v: changed)Wnew[v] = W[v];
    for(int i = l; i < pos; i++){
        if(T[i] == 1)Wnew[id[i]] = val[i];
    }
    for(auto v: changed)if(Wnew[v] >= val[pos]){
        g[Find(U[v])].push_back(Find(V[v]));
        g[Find(V[v])].push_back(Find(U[v]));
    }
    ans[pos] = dfs(Find(id[pos]), pos);
    for(auto v: changed){
        g[Find(U[v])].clear();
        g[Find(V[v])].clear();
    }
}

int main() {
    cin >> n >> m;
    for(int i = 1; i <= n; i++)vis[i] = -1;
    set<int, cmp> st;
    for(int i = 1; i <= m; i++){
        cin >> U[i] >> V[i] >> W[i];
        st.insert(i);
    }
    cin >> q;
    for(int i = 0; i < q; i++){
        cin >> T[i] >> id[i] >> val[i];
    }
    for(int l = 0; l < q; l += blsz){
        int r = min(l + blsz, q);

        // solving queries

        vector<int> changed;
        vector<pair<int, int>> queries;
        for(int i = l; i < r; i++){
            if(T[i] == 1){
                changed.push_back(id[i]);
                chk[id[i]] = 1;
            }
            else queries.push_back({val[i], i});
        }
        sort(queries.begin(), queries.end());
        reverse(queries.begin(), queries.end());
        int ptr = 0;
        for(int i = 1; i <= n; i++)up[i] = -1;
        for(auto v: st){
            if(ptr < queries.size() && queries[ptr].first > W[v])solve_query(l, queries[ptr++].second, changed);
            if(!chk[v])Union(U[v], V[v]);
        }
        while(ptr < queries.size())solve_query(l, queries[ptr++].second, changed);

        // update and reset. also prints answers

        for(int i = l; i < r; i++){
            if(T[i] == 1){
                chk[id[i]] = 0;

                st.erase(id[i]);
                W[id[i]] = val[i];
                st.insert(id[i]);
            }
            else cout << ans[i] << "\n";
        }
    }
}

Compilation message

bridges.cpp: In function 'int main()':
bridges.cpp:95:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |             if(ptr < queries.size() && queries[ptr].first > W[v])solve_query(l, queries[ptr++].second, changed);
      |                ~~~~^~~~~~~~~~~~~~~~
bridges.cpp:98:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |         while(ptr < queries.size())solve_query(l, queries[ptr++].second, changed);
      |               ~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6748 KB Output is correct
2 Correct 2 ms 6760 KB Output is correct
3 Incorrect 368 ms 7088 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3018 ms 12196 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3048 ms 10596 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 609 ms 14304 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3018 ms 12196 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6748 KB Output is correct
2 Correct 2 ms 6760 KB Output is correct
3 Incorrect 368 ms 7088 KB Output isn't correct
4 Halted 0 ms 0 KB -