Submission #269885

#	Time	Username	Problem	Language	Result	Execution time	Memory
269885		evpipis	Bridges (APIO19_bridges)	C++11	100 / 100	2554 ms	9372 KiB

bridges

#include <bits/stdc++.h>
using namespace std;

#define ASK 2
#define UPD 1

#define pb push_back

const int len = 1e5+5;

int block[len], help_wei[len], vis[len], out[len], cnt, n;
vector<int> sorted, adj[len];

struct{
    int a, b, c;
} edge[len];

struct{
    int tp, a, b;
} query[len];

bool comp_edge(int a, int b){
    return (edge[a].c > edge[b].c);
}

bool comp_ask(int a, int b){
    return (query[a].b > query[b].b);
}

struct{
    int par[len], ran[len];

    void init(){
        for (int i = 1; i <= n; i++)
            par[i] = i, ran[i] = 1;
    }

    int fin(int i){
        if (i == par[i]) return i;
        return par[i] = fin(par[i]);
    }

    void join(int i, int j){
        i = fin(i), j = fin(j);
        if (i == j) return;

        if (ran[i] > ran[j])
            ran[i] += ran[j], par[j] = i;
        else
            ran[j] += ran[i], par[i] = j;
    }

    void print(){
        for (int i = 1; i <= n; i++)
            printf("par[%d] = %d\n", i, fin(i));
    }
} dsu;

int dfs(int u){
    vis[u] = cnt;

    int ans = dsu.ran[u];
    for (auto v: adj[u])
        if (vis[v] != cnt)
            ans += dfs(v);

    return ans;
}

void solve(int l, int r){
    vector<int> ask, spec;

    for (int i = l; i <= r; i++){
        int tp = query[i].tp, a = query[i].a, b = query[i].b;

        if (tp == ASK){
            ask.pb(i);
        }
        else{
            if (!block[a])
                spec.pb(a), block[a] = 1;
        }
    }

    dsu.init();

    sort(ask.begin(), ask.end(), comp_ask);
    for (int i = 0, j = 0; i < ask.size(); i++){
        int st = query[ask[i]].a, lo = query[ask[i]].b;

        while (j < sorted.size() && edge[sorted[j]].c >= lo){
            if (!block[sorted[j]])
                dsu.join(edge[sorted[j]].a, edge[sorted[j]].b);
            j++;
        }

        for (int d = 0; d < spec.size(); d++)
            help_wei[spec[d]] = edge[spec[d]].c;
        for (int d = l; d < ask[i]; d++)
            if (query[d].tp == UPD)
                help_wei[query[d].a] = query[d].b;
        for (int d = 0; d < spec.size(); d++){
            int a = edge[spec[d]].a, b = edge[spec[d]].b, c = help_wei[spec[d]];
            if (c >= lo)
                adj[dsu.fin(a)].pb(dsu.fin(b)), adj[dsu.fin(b)].pb(dsu.fin(a));
        }

        cnt++;
        out[ask[i]] = dfs(dsu.fin(st));

        for (int d = 0; d < spec.size(); d++){
            int a = dsu.fin(edge[spec[d]].a), b = dsu.fin(edge[spec[d]].b), c = help_wei[spec[d]];
            adj[a].clear();
            adj[b].clear();
        }
    }

    for (int i = l; i <= r; i++){
        int tp = query[i].tp, a = query[i].a, b = query[i].b;

        if (tp == UPD)
            edge[a].c = b;
    }

    vector<int> help;
    for (int i = 0; i < sorted.size(); i++)
        if (!block[sorted[i]])
            help.pb(sorted[i]);
    sorted.clear();

    sort(spec.begin(), spec.end(), comp_edge);
    for (int i = 0, j = 0; i < spec.size() || j < help.size(); ){
        if (j == help.size())
            sorted.pb(spec[i++]);
        else if (i == spec.size())
            sorted.pb(help[j++]);
        else if (edge[help[j]].c >= edge[spec[i]].c)
            sorted.pb(help[j++]);
        else
            sorted.pb(spec[i++]);
    }

    for (int i = 0; i < spec.size(); i++)
        block[spec[i]] = 0;
}

int main(){
    int m, q, k;
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; i++)
        scanf("%d %d %d", &edge[i].a, &edge[i].b, &edge[i].c);

    scanf("%d", &q);
    for (int i = 0; i < q; i++)
        scanf("%d %d %d", &query[i].tp, &query[i].a, &query[i].b);

    for (int i = 1; i <= m; i++)
        sorted.pb(i);
    sort(sorted.begin(), sorted.end(), comp_edge);

    k = sqrt(m+n);
    for (int i = 0; i < q; i+=k)
        solve(i, min(i+k-1, q-1));

    for (int i = 0; i < q; i++)
        if (query[i].tp == ASK)
            printf("%d\n", out[i]);
    return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'void solve(int, int)':
bridges.cpp:74:47: warning: unused variable 'b' [-Wunused-variable]
   74 |         int tp = query[i].tp, a = query[i].a, b = query[i].b;
      |                                               ^
bridges.cpp:88:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |     for (int i = 0, j = 0; i < ask.size(); i++){
      |                            ~~^~~~~~~~~~~~
bridges.cpp:91:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |         while (j < sorted.size() && edge[sorted[j]].c >= lo){
      |                ~~^~~~~~~~~~~~~~~
bridges.cpp:97:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |         for (int d = 0; d < spec.size(); d++)
      |                         ~~^~~~~~~~~~~~~
bridges.cpp:102:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |         for (int d = 0; d < spec.size(); d++){
      |                         ~~^~~~~~~~~~~~~
bridges.cpp:111:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |         for (int d = 0; d < spec.size(); d++){
      |                         ~~^~~~~~~~~~~~~
bridges.cpp:112:77: warning: unused variable 'c' [-Wunused-variable]
  112 |             int a = dsu.fin(edge[spec[d]].a), b = dsu.fin(edge[spec[d]].b), c = help_wei[spec[d]];
      |                                                                             ^
bridges.cpp:126:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  126 |     for (int i = 0; i < sorted.size(); i++)
      |                     ~~^~~~~~~~~~~~~~~
bridges.cpp:132:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |     for (int i = 0, j = 0; i < spec.size() || j < help.size(); ){
      |                            ~~^~~~~~~~~~~~~
bridges.cpp:132:49: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |     for (int i = 0, j = 0; i < spec.size() || j < help.size(); ){
      |                                               ~~^~~~~~~~~~~~~
bridges.cpp:133:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |         if (j == help.size())
      |             ~~^~~~~~~~~~~~~~
bridges.cpp:135:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |         else if (i == spec.size())
      |                  ~~^~~~~~~~~~~~~~
bridges.cpp:143:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  143 |     for (int i = 0; i < spec.size(); i++)
      |                     ~~^~~~~~~~~~~~~
bridges.cpp: In function 'int main()':
bridges.cpp:149:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  149 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
bridges.cpp:151:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  151 |         scanf("%d %d %d", &edge[i].a, &edge[i].b, &edge[i].c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:153:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  153 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
bridges.cpp:155:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  155 |         scanf("%d %d %d", &query[i].tp, &query[i].a, &query[i].b);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 16 / 16
• Subtask 3: 17 / 17
• Subtask 4: 14 / 14
• Subtask 5: 13 / 13
• Subtask 6: 27 / 27