Submission #269837

#	Time	Username	Problem	Language	Result	Execution time	Memory
269837		evpipis	Bridges (APIO19_bridges)	C++11	100 / 100	2829 ms	13552 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){
    //printf("solving bucket: l = %d, r = %d\n", l, 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;

        //printf(" --- ask now: st = %d, lo = %d --- \n", st, lo);

        while (j < sorted.size() && edge[sorted[j]].c >= lo){
            if (!block[sorted[j]])
                //printf("added edge: (%d, %d)\n", edge[sorted[j]].a, edge[sorted[j]].b),
                dsu.join(edge[sorted[j]].a, edge[sorted[j]].b);
            j++;
        }

        //printf("ask = %d, st = %d, lo = %d\n", ask[i], st, lo);
        //dsu.print();

        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(q);
    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:76:47: warning: unused variable 'b' [-Wunused-variable]
   76 |         int tp = query[i].tp, a = query[i].a, b = query[i].b;
      |                                               ^
bridges.cpp:90:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |     for (int i = 0, j = 0; i < ask.size(); i++){
      |                            ~~^~~~~~~~~~~~
bridges.cpp:95:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |         while (j < sorted.size() && edge[sorted[j]].c >= lo){
      |                ~~^~~~~~~~~~~~~~~
bridges.cpp:105:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |         for (int d = 0; d < spec.size(); d++)
      |                         ~~^~~~~~~~~~~~~
bridges.cpp:110:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |         for (int d = 0; d < spec.size(); d++){
      |                         ~~^~~~~~~~~~~~~
bridges.cpp:119:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |         for (int d = 0; d < spec.size(); d++){
      |                         ~~^~~~~~~~~~~~~
bridges.cpp:120:77: warning: unused variable 'c' [-Wunused-variable]
  120 |             int a = dsu.fin(edge[spec[d]].a), b = dsu.fin(edge[spec[d]].b), c = help_wei[spec[d]];
      |                                                                             ^
bridges.cpp:134:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  134 |     for (int i = 0; i < sorted.size(); i++)
      |                     ~~^~~~~~~~~~~~~~~
bridges.cpp:140:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  140 |     for (int i = 0, j = 0; i < spec.size() || j < help.size(); ){
      |                            ~~^~~~~~~~~~~~~
bridges.cpp:140:49: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  140 |     for (int i = 0, j = 0; i < spec.size() || j < help.size(); ){
      |                                               ~~^~~~~~~~~~~~~
bridges.cpp:141:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  141 |         if (j == help.size())
      |             ~~^~~~~~~~~~~~~~
bridges.cpp:143:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  143 |         else if (i == spec.size())
      |                  ~~^~~~~~~~~~~~~~
bridges.cpp:151:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  151 |     for (int i = 0; i < spec.size(); i++)
      |                     ~~^~~~~~~~~~~~~
bridges.cpp: In function 'int main()':
bridges.cpp:157:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  157 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
bridges.cpp:159:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  159 |         scanf("%d %d %d", &edge[i].a, &edge[i].b, &edge[i].c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:161:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  161 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
bridges.cpp:163:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  163 |         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