oj.uz

Submission #252420

# Submission time Handle Problem Language Result Execution time Memory
252420 2020-07-25T14:03:15 Z Erkhemkhuu Bridges (APIO19_bridges) C++17
13 / 100
 364 ms 36216 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define F first
#define S second
typedef pair <ll, ll> pll;
const ll sN = 1005;
const ll N = 100005;
bool vis[N];
vector <vector <ll> > adj(N);
ll tree[N * 4], sz[N], par[N], out[N];
tuple <ll, ll, ll> brid[N];
vector <ll> wp[sN][sN];
struct trio {
    ll v, u, w;
} edges[N];
struct trio1 {
    ll v, w, ind;
} queries[N];
bool comp(trio &a, trio &b) {
    return (a.w > b.w);
}
bool comp1(trio1 &a, trio1 &b) {
    return (a.w > b.w);
}
void build(ll node, ll l, ll r) {
    if(l == r) {
        tree[node] = edges[l].w;
        return;
    }
    ll mid = (l + r) / 2;
    build(node * 2, l, mid);
    build(node * 2 + 1, mid + 1, r);
    tree[node] = min(tree[node * 2], tree[node * 2 + 1]);
    return;
}
void update(ll node, ll l, ll r, ll idx, ll val) {
    if(l == r) {
        tree[node] = val;
        return;
    }
    ll mid = (l + r) / 2;
    if(l <= idx && idx <= mid) update(node * 2, l, mid, idx, val);
    else update(node * 2 + 1, mid + 1, r, idx, val);
    tree[node] = min(tree[node * 2], tree[node * 2 + 1]);
    return;
}
ll get(ll x) {
    return ((x == par[x]) ? (x) : (par[x] = get(par[x])));
}
void unite(ll v, ll u) {
    ll parv = get(v);
    ll paru = get(u);
    if(parv == paru) return;
    if(sz[parv] < sz[paru]) swap(parv, paru);
    sz[parv] += sz[paru];
    par[paru] = parv;
    return;
}
void init() {
    for(ll i = 0; i < N; i++) {
        sz[i] = 1;
        par[i] = i;
    }
    return;
}
ll dfs(ll v, ll w) {
    ll ans = 1;
    vis[v] = true;
    for(auto &u: adj[v])
        for(auto &x: wp[v][u])
            if(!vis[u] && w <= x) ans += dfs(u, w);
    return ans;
}
int main() {
    ll n, m, i, v, u, w, q, t, l, r;
    bool flag = true;
    cin >> n >> m;
    flag &= (m != n - 1);
    for(i = 1; i <= m; i++) {
        cin >> v >> u >> w;
        adj[v].pb(u);
        adj[u].pb(v);
        flag &= (u == i + 1 && v == i);
        if(n <= 1000 && m <= 1000) {
            wp[v][u].pb(w);
            wp[u][v].pb(w);
            brid[i] = {v, u, wp[v][u].size() - 1};
        }
        edges[i] = {v, u, w};
    }
    cin >> q;
    if(n <= 1000 && m <= 1000 && q <= 10000) {
        while(q--) {
            cin >> t >> l >> r;
            if(t == 1) {
                auto temp = brid[l];
                ll x = get <0> (temp);
                ll y = get <1> (temp);
                ll z = get <2> (temp);
                wp[x][y][z] = wp[y][x][z] = r;
            }
            else {
                memset(vis, false, sizeof(vis));
                cout << dfs(l, r) << "\n";
            }
        }
        return 0;
    }
    bool flag1 = true;
    for(i = 1; i <= q; i++) {
        cin >> t >> l >> r;
        queries[i] = {l, r, i};
    }
    for(i = 1; i <= n; i++) {
        par[i] = i;
        sz[i] = 1;
    }
    sort(edges + 1, edges + m + 1, comp);
    sort(queries + 1, queries + q + 1, comp1);
    ll cur = 1;
    for(i = 1; i <= q; i++) {
        while(cur <= n && edges[cur].w >= queries[i].w) {
            unite(edges[cur].v, edges[i].u);
            cur++;
        }
        out[queries[i].ind] = sz[get(queries[i].v)];
    }
    for(i = 1; i <= q; i++)
        cout << out[i] << "\n";
    /*
    if(flag) {
        build(1, 1, n);
        while(q--) {
            cin >> t >> l >> r;
            if(t == 1) update(1, 1, n, l, r);
            else {

            }
        }
        return 0;
    }
    */
    return 0;
}

Compilation message

bridges.cpp: In function 'int main()':
bridges.cpp:112:10: warning: unused variable 'flag1' [-Wunused-variable]
     bool flag1 = true;
          ^~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 26496 KB Output is correct
2 Correct 15 ms 26496 KB Output is correct
3 Correct 125 ms 26624 KB Output is correct
4 Correct 85 ms 26616 KB Output is correct
5 Correct 53 ms 26496 KB Output is correct
6 Correct 53 ms 26496 KB Output is correct
7 Correct 51 ms 26496 KB Output is correct
8 Correct 52 ms 26496 KB Output is correct
9 Correct 50 ms 26496 KB Output is correct
10 Correct 52 ms 26496 KB Output is correct
11 Correct 67 ms 26584 KB Output is correct
12 Correct 64 ms 26496 KB Output is correct
13 Correct 62 ms 26496 KB Output is correct
14 Correct 52 ms 26496 KB Output is correct
15 Correct 57 ms 26496 KB Output is correct
16 Correct 55 ms 26496 KB Output is correct
17 Correct 52 ms 26496 KB Output is correct

Subtask #2
0 / 16.0

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

Subtask #3
0 / 17.0

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

Subtask #4
0 / 14.0

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

Subtask #5
0 / 13.0

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

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 26496 KB Output is correct
2 Correct 15 ms 26496 KB Output is correct
3 Correct 125 ms 26624 KB Output is correct
4 Correct 85 ms 26616 KB Output is correct
5 Correct 53 ms 26496 KB Output is correct
6 Correct 53 ms 26496 KB Output is correct
7 Correct 51 ms 26496 KB Output is correct
8 Correct 52 ms 26496 KB Output is correct
9 Correct 50 ms 26496 KB Output is correct
10 Correct 52 ms 26496 KB Output is correct
11 Correct 67 ms 26584 KB Output is correct
12 Correct 64 ms 26496 KB Output is correct
13 Correct 62 ms 26496 KB Output is correct
14 Correct 52 ms 26496 KB Output is correct
15 Correct 57 ms 26496 KB Output is correct
16 Correct 55 ms 26496 KB Output is correct
17 Correct 52 ms 26496 KB Output is correct
18 Incorrect 243 ms 33400 KB Output isn't correct
19 Halted 0 ms 0 KB -