oj.uz

Submission #130579

# Submission time Handle Problem Language Result Execution time Memory
130579 2019-07-15T15:38:38 Z osaaateiasavtnl Bridges (APIO19_bridges) C++17
30 / 100
 3000 ms 15648 KB 
#include<bits/stdc++.h>
using namespace std;
#define app push_back
struct Edge {
    int u, v, c;
};            
const int K = 800;
const int N = 1e5 + 7;
int ans[N];
Edge ed[N];
int par[N], cnt[N];
int root(int u) {
    if (u == par[u]) return u;
    else return par[u] = root(par[u]);
}   
void merge(int u, int v) {
    u = root(u); v = root(v);
    if (u == v) return;
    if (cnt[v] < cnt[u]) swap(u, v);
    par[u] = v; cnt[v] += cnt[u];
}   
struct Quer {
    int t, i, c;
};
Quer d[N];
bool comp(int i, int j) {
    return ed[i].c > ed[j].c;
}   
bool comp_quer(int i, int j) {
    return d[i].c > d[j].c;
}   
vector <int> g[N];
bool used[N];

bool dfs_used[N];
vector <int> vis;
int dfs(int u) {
    dfs_used[u] = 1;
    vis.app(u);
    int ans = cnt[u];
    for (int v : g[u]) {
        if (!dfs_used[v]) {
            ans += dfs(v);
        }   
    }   
    return ans;
}   
int mem[N];

const int C = N << 1;

vector <int> v[C];

signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif                             
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        cin >> ed[i].u >> ed[i].v >> ed[i].c;
    }   
    int q;
    cin >> q;
    for (int i = 0; i < q; ++i) {
        cin >> d[i].t >> d[i].i >> d[i].c;
        if (d[i].t == 1) --d[i].i;
    }   
    vector <int> c;
    for (int i = 0; i < m; ++i) {
        c.app(ed[i].c);
    }   
    for (int i = 0; i < q; ++i) {
        c.app(d[i].c);
    }   
    sort(c.begin(), c.end()); 
    c.resize(unique(c.begin(), c.end()) - c.begin());
    for (int i = 0; i < m; ++i) {
        ed[i].c = lower_bound(c.begin(), c.end(), ed[i].c) - c.begin();
    }   
    for (int i = 0; i < q; ++i) {
        d[i].c = lower_bound(c.begin(), c.end(), d[i].c) - c.begin();
    }   
    for (int a = 0; ; ++a) {
        if (a * K >= q) break;
        memset(used, 0, sizeof used);
        vector <int> quer;
        for (int b = 0; b < K; ++b) {
            int i = a * K + b;
            if (i >= q) break;
            if (d[i].t == 1) {
                used[d[i].i] = 1;
            }
            else {
                quer.app(i);
            }   
        }   
        for (int i = 0; i < C; ++i) {
            v[i].clear();
        }   
        vector <int> us;
        for (int i = 0; i < m; ++i) {
            if (used[i]) {
                us.app(i);
            }   
            else {
                v[ed[i].c].app(i);
            }   
        }   
        sort(quer.begin(), quer.end(), comp_quer);
        for (int i = 1; i <= n; ++i) {
            par[i] = i; cnt[i] = 1;
        }
        for (int i = 0; i < m; ++i) {
            mem[i] = ed[i].c;
        }   
        int ptr = C - 1;
        for (int i : quer) {
            while (ptr >= d[i].c) {
                for (int e : v[ptr]) {
                    merge(ed[e].u, ed[e].v);
                }   
                --ptr;
            }
            for (int b = 0; b < K; ++b) {
                int j = a * K + b;
                if (j >= q) break;
                int e = d[j].i;
                if (d[j].t == 1) ed[e].c = mem[e];
            }   
            for (int b = 0; b < K; ++b) {
                int j = a * K + b;
                if (j >= i) break;
                int e = d[j].i;
                if (d[j].t == 1) ed[e].c = d[j].c;
            }               
            for (int e : us) {
                if (ed[e].c >= d[i].c) {
                    int u = root(ed[e].u), v = root(ed[e].v);
                    g[u].app(v); g[v].app(u);
                }
            }
            ans[i] = dfs(root(d[i].i));
            for (int e : vis) {
                dfs_used[e] = 0;
            }   
            vis.clear();
            for (int e : us) {
                int u = root(ed[e].u), v = root(ed[e].v);
                g[u].clear(); g[v].clear();
            }              
        }   
        for (int b = 0; b < K; ++b) {
            int i = a * K + b;
            if (i >= q) break;
            if (d[i].t == 1) {
                ed[d[i].i].c = d[i].c;
            }   
        }               
    }   
    for (int i = 0; i < q; ++i) {
        if (d[i].t == 2) {
            cout << ans[i] << '\n';
        }
    }   
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7544 KB Output is correct
2 Correct 9 ms 7548 KB Output is correct
3 Correct 83 ms 7932 KB Output is correct
4 Correct 33 ms 7800 KB Output is correct
5 Correct 46 ms 7800 KB Output is correct
6 Correct 52 ms 7800 KB Output is correct
7 Correct 46 ms 7800 KB Output is correct
8 Correct 47 ms 7800 KB Output is correct
9 Correct 50 ms 7800 KB Output is correct
10 Correct 49 ms 7800 KB Output is correct
11 Correct 49 ms 7800 KB Output is correct
12 Correct 48 ms 7800 KB Output is correct
13 Correct 55 ms 7836 KB Output is correct
14 Correct 51 ms 7800 KB Output is correct
15 Correct 49 ms 7800 KB Output is correct
16 Correct 48 ms 7804 KB Output is correct
17 Correct 47 ms 7800 KB Output is correct

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2925 ms 15552 KB Output is correct
2 Correct 2753 ms 15608 KB Output is correct
3 Correct 2920 ms 15508 KB Output is correct
4 Correct 2829 ms 15648 KB Output is correct
5 Correct 2893 ms 15532 KB Output is correct
6 Execution timed out 3038 ms 14348 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2424 ms 14196 KB Output is correct
2 Correct 1670 ms 12184 KB Output is correct
3 Correct 2650 ms 14372 KB Output is correct
4 Correct 2418 ms 14268 KB Output is correct
5 Correct 258 ms 9844 KB Output is correct
6 Correct 2493 ms 14148 KB Output is correct
7 Correct 2246 ms 14196 KB Output is correct
8 Correct 2101 ms 14188 KB Output is correct
9 Correct 1305 ms 12668 KB Output is correct
10 Correct 1271 ms 12628 KB Output is correct
11 Correct 1504 ms 15308 KB Output is correct
12 Correct 1395 ms 15460 KB Output is correct

Subtask #4
0 / 14.0

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

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2925 ms 15552 KB Output is correct
2 Correct 2753 ms 15608 KB Output is correct
3 Correct 2920 ms 15508 KB Output is correct
4 Correct 2829 ms 15648 KB Output is correct
5 Correct 2893 ms 15532 KB Output is correct
6 Execution timed out 3038 ms 14348 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7544 KB Output is correct
2 Correct 9 ms 7548 KB Output is correct
3 Correct 83 ms 7932 KB Output is correct
4 Correct 33 ms 7800 KB Output is correct
5 Correct 46 ms 7800 KB Output is correct
6 Correct 52 ms 7800 KB Output is correct
7 Correct 46 ms 7800 KB Output is correct
8 Correct 47 ms 7800 KB Output is correct
9 Correct 50 ms 7800 KB Output is correct
10 Correct 49 ms 7800 KB Output is correct
11 Correct 49 ms 7800 KB Output is correct
12 Correct 48 ms 7800 KB Output is correct
13 Correct 55 ms 7836 KB Output is correct
14 Correct 51 ms 7800 KB Output is correct
15 Correct 49 ms 7800 KB Output is correct
16 Correct 48 ms 7804 KB Output is correct
17 Correct 47 ms 7800 KB Output is correct
18 Correct 2925 ms 15552 KB Output is correct
19 Correct 2753 ms 15608 KB Output is correct
20 Correct 2920 ms 15508 KB Output is correct
21 Correct 2829 ms 15648 KB Output is correct
22 Correct 2893 ms 15532 KB Output is correct
23 Execution timed out 3038 ms 14348 KB Time limit exceeded
24 Halted 0 ms 0 KB -