oj.uz

Submission #130578

# Submission time Handle Problem Language Result Execution time Memory
130578 2019-07-15T15:37:28 Z osaaateiasavtnl Bridges (APIO19_bridges) C++17
30 / 100
 3000 ms 15416 KB 
#include<bits/stdc++.h>
using namespace std;
#define app push_back
struct Edge {
    int u, v, c;
};            
const int K = 400;
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 7544 KB Output is correct
3 Correct 63 ms 8056 KB Output is correct
4 Correct 35 ms 7800 KB Output is correct
5 Correct 47 ms 7844 KB Output is correct
6 Correct 45 ms 7800 KB Output is correct
7 Correct 45 ms 7800 KB Output is correct
8 Correct 47 ms 7800 KB Output is correct
9 Correct 54 ms 7928 KB Output is correct
10 Correct 52 ms 7800 KB Output is correct
11 Correct 47 ms 7800 KB Output is correct
12 Correct 48 ms 7800 KB Output is correct
13 Correct 50 ms 7800 KB Output is correct
14 Correct 49 ms 7800 KB Output is correct
15 Correct 49 ms 7800 KB Output is correct
16 Correct 45 ms 7800 KB Output is correct
17 Correct 46 ms 7928 KB Output is correct

Subtask #2
0 / 16.0

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

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2118 ms 14280 KB Output is correct
2 Correct 1074 ms 12120 KB Output is correct
3 Correct 2081 ms 14452 KB Output is correct
4 Correct 2121 ms 14188 KB Output is correct
5 Correct 272 ms 9860 KB Output is correct
6 Correct 2169 ms 14320 KB Output is correct
7 Correct 2151 ms 14120 KB Output is correct
8 Correct 2192 ms 14332 KB Output is correct
9 Correct 1510 ms 12660 KB Output is correct
10 Correct 1530 ms 12628 KB Output is correct
11 Correct 1660 ms 15340 KB Output is correct
12 Correct 1568 ms 15368 KB Output is correct

Subtask #4
0 / 14.0

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

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3032 ms 15416 KB Time limit exceeded
2 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 7544 KB Output is correct
3 Correct 63 ms 8056 KB Output is correct
4 Correct 35 ms 7800 KB Output is correct
5 Correct 47 ms 7844 KB Output is correct
6 Correct 45 ms 7800 KB Output is correct
7 Correct 45 ms 7800 KB Output is correct
8 Correct 47 ms 7800 KB Output is correct
9 Correct 54 ms 7928 KB Output is correct
10 Correct 52 ms 7800 KB Output is correct
11 Correct 47 ms 7800 KB Output is correct
12 Correct 48 ms 7800 KB Output is correct
13 Correct 50 ms 7800 KB Output is correct
14 Correct 49 ms 7800 KB Output is correct
15 Correct 49 ms 7800 KB Output is correct
16 Correct 45 ms 7800 KB Output is correct
17 Correct 46 ms 7928 KB Output is correct
18 Execution timed out 3032 ms 15416 KB Time limit exceeded
19 Halted 0 ms 0 KB -