Submission #914612

#	Time	Username	Problem	Language	Result	Execution time	Memory
914612		coding_monk3	Bridges (APIO19_bridges)	C++17	100 / 100	2609 ms	10244 KiB

bridges

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

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

// Miscellanous
#define gc getchar_unlocked
#define ll long long
#define ull unsigned long long
#define si(x)	scanf("%d",&x)
#define si2(x,y) scanf("%d %d",&x,&y)
#define sl(x)	scanf("%lld",&x)
#define sl2(x,y) scanf("%lld %lld",&x,&y)
#define sstr(s)	cin >> s
#define pi(x)	printf("%d\n",x)
#define pi2(x,y)	printf("%d %d\n",x,y)
#define pl(x)	printf("%lld\n",x)
#define pl2(x,y)	printf("%lld %lld\n",x,y)
#define ps(s)	cout << s << endl
#define py	    printf("YES\n")
#define pn	    printf("NO\n")
#define pnl	    printf("\n")
#define pb push_back
#define ff first
#define ss second
#define sz(v) (int)v.size()
#define all(v) v.begin(),v.end()
#define sortv(v) sort(all(v))
#define revsort(v) sort(v.rbegin(),v.rend())
#define reverse(v) reverse(all(v))
#define alla(arr,sz) arr,arr+sz
#define sorta(arr,sz) sort(alla(arr,sz))
#define reversea(arr,sz) reverse(alla(arr,sz))
#define cta(x,v) count(alla(arr,sz),x)
#define ct(x,v) count(all(v),x)
#define cto(v) count_if(all(v),[] (int a) {return a%2 == 1;})
#define cte(v) count_if(all(v),[] (int a) {return a%2 == 0;})

#define MAX(a,b) a = max(a,b)
#define MIN(a,b) a = min(a,b)
#define clr(x) memset(x, 0, sizeof(x))

// Loops
#define loop(i,s,e) for (int (i)=(s);(i)<(e);++(i))
#define loope(i,s,e) for (int (i)=(s);(i)<=(e);++(i))
#define forc(c,s,e) for (char (c)=(s);(c)<=(e);++(c))
#define forr(i,s,e) for (int (i)=(s);(i)>=(e);--(i))
#define foreach(val,cont) for (auto &(val) : (cont))
#define rep(i,n) loop(i,0,n)
#define repn(i,n) loope(i,1,n)

// Constants
#define PI 3.1415926535897932384626
#define sqr(x) ((x) * 1ll * (x))
const int mod = 1000000007;

// Containers
typedef pair<int, int>	    pii;
typedef pair<ll, ll>	    pll;
typedef vector<int>		    vi;
typedef vector<ll>		    vl;
typedef vector<pii>		    vpii;
typedef vector<pll>		    vpll;
typedef vector<vi>		    vvi;
typedef vector<vl>		    vvl;
typedef pair<string,string> pss;
typedef map<int, int>	    mii;

// Input Output
struct edge
{
    int u,v,wt;

    bool operator<(const edge &x) const {return wt < x.wt;}

    void read() {scanf("%d %d %d" , &u, &v, &wt);}
};

#define takei(a) int a; si(a)
#define takei2(a,b) int a,b; si2(a,b)
#define takel(a) ll a; sl(a)
#define takel2(a,b) ll a,b; sl2(a,b)
#define takearri0(n,a)  vi a(n); rep(i,n) si(a[i]) 
#define takearri1(n,a)  vi a(n+1); a[0] = 0; repn(i,n) si(a[i])
#define takearrl0(n,a)  vl a(n); rep(i,n) sl(a[i]) 
#define takearrl1(n,a)  vl a(n+1); a[0] = 0ll; repn(i,n) sl(a[i]) 

// Debug
void _print(int t) {cerr << t;}
void _print(ll t) {cerr << t;}
void _print(string t) {cerr << t;}
void _print(char t) {cerr << t;}
void _print(double t) {cerr << t;}
void _print(ull t) {cerr << t;}
void _print(edge t) {cerr << "[ " << '{' << t.u << ',' << t.v << "} " << t.wt << " ]";}

template <class T, class V> void _print(pair <T, V> p);
template <class T> void _print(vector <T> v);

template <class T> void _print(unordered_set <T> v);
template <class T> void _print(unordered_multiset <T> v);
template <class T> void _print(set <T> v);
template <class T> void _print(multiset <T> v);

template <class T, class V> void _print(unordered_map <T, V> v);
template <class T, class V> void _print(unordered_multimap <T, V> v);
template <class T, class V> void _print(map <T, V> v);
template <class T, class V> void _print(multimap <T, V> v);

template <class T, class V> void _print(pair <T, V> p) {cerr << "{"; _print(p.ff); cerr << ","; _print(p.ss); cerr << "}";}
template <class T> void _print(vector <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}

template <class T> void _print(unordered_set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(unordered_multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}

template <class T, class V> void _print(unordered_map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _print(unordered_multimap <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _print(multimap <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}

#ifndef ONLINE_JUDGE
#define deb(x) cerr << #x << " = ";  _print(x); cerr << endl;
#else
#define deb(x)
#endif


inline string inttostr(ll a){
  char x[100];
  sprintf(x,"%lld",a); string s = x;
  return s;
}

inline ll strtoint(string a){
  char x[100]; ll res;
  strcpy(x,a.c_str()); sscanf(x,"%lld",&res);
  return res;
}

inline string getstr(void){
  char x[1000005];
  scanf("%s",x); string s = x;
  return s;
}

inline string uppercase(string s){
  int n = sz(s); 
  rep(i,n) if (s[i] >= 'a' && s[i] <= 'z') s[i] = s[i] - 'a' + 'A';
  return s;
}
 
inline string lowercase(string s){
  int n = sz(s); 
  rep(i,n) if (s[i] >= 'A' && s[i] <= 'Z') s[i] = s[i] - 'A' + 'a';
  return s;
}

// ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

// Link --> https://oj.uz/problem/view/APIO19_bridges
// Explanation --> https://codeforces.com/blog/entry/67129#:~:text=Brief%20Outline%3A%20Divide,DSU%20with%20rollbacks.
// https://codeforces.com/blog/entry/67129#:~:text=You%20don%27t%20need,vertex%20with%20weight.)


// Divide the queries into sqrt(q) blocks. 
// For each block, AT MOST sqrt(q) edges have weights changed within the block. 

// Sort all the queries by decreasing weight in the block, and maintain a DSU while 
// adding edges that are ** UNCHANGED ** within the block one-by-one in 
// DECREASING order of WEIGHT

// And to answer each query, just simply connect the extra "CHANGED" edges 
// on the COMPRESSED VERTICES and run DFS, i.e. just regard a connected component 
// as a single vertex with weight 

const int MAXN = 5e4;
vi adj[MAXN+1];
int color[MAXN+1];
int size_[MAXN+1] , parent[MAXN+1];
bool vis2[MAXN+1]; 

// DSU ----------------------------------------------------------
void reset(int n)
{
    repn(i,n) size_[i] = 1;
    repn(i,n) parent[i] = i;
}

int find_par(int node)
{
    if(parent[node] == node) return node;
    return parent[node] = find_par(parent[node]);
}

void size_union(int x, int y)
{
    x = find_par(x);
    y = find_par(y);
    if(x == y) return;
    if(size_[x] < size_[y]) {parent[x] = y; size_[y] += size_[x];}
    else {parent[y] = x; size_[x] += size_[y];}
}

bool connected(int x, int y)
{
    return find_par(x) == find_par(y);
}
// --------------------------------------------------------------

void add_edge(int u, int v)
{
    adj[u].pb(v);
    adj[v].pb(u);
}

void dfs(int u, int &ans)
{
    if(vis2[u]) return;
    vis2[u] = 1;
    ans += size_[u];

    for(auto v : adj[u]) dfs(v,ans);
}

int main()
{
    const int B_SIZE = 500;
    takei2(n,m); 
    vector<edge> edges(m+1);
    
    repn(i,m) edges[i].read();

    bool change[m+1];
    bool chk[m+1];
    vi to_add[B_SIZE];
    int answer[B_SIZE];

    takei(q); 
    for (int l = 0; l < q; l += B_SIZE)
    {
        int r = min(q - 1 , l + B_SIZE - 1);    
        vvi cur_q(r-l+1);
        vi ask, upd;
        clr(change);
        rep(i,r-l+1)
        {
            takei(t); 
            takei2(id,wt);
            cur_q[i] = {t,id,wt};
            if(t == 1) change[id] = 1, upd.pb(i);
            else ask.pb(i);
        }

        rep(i,r-l+1)
        {
            int &t = cur_q[i][0] , &id = cur_q[i][1] , &wt = cur_q[i][2];

            if(t == 1) edges[id].wt = wt;
            else 
            {
                to_add[i].clear();
                for(auto &j : upd) chk[cur_q[j][1]] = 0;

                for(auto &j : upd)
                {
                    int id2 = cur_q[j][1];
                    if(edges[id2].wt >= wt and !chk[id2]) to_add[i].pb(id2) , chk[id2] = 1;
                }
            }
        }

        vi unchanged;
        repn(i,m) if(!change[i]) unchanged.pb(i);
    
        sort(all(unchanged) , [&] (int i, int j) {return edges[i].wt > edges[j].wt;});
        sort(all(ask) , [&] (int i, int j) {return cur_q[i][2] > cur_q[j][2];});

        reset(n);
        int j = 0, s = sz(unchanged);
        for(auto &i : ask)
        {
            int start = cur_q[i][1];
            int car_wt = cur_q[i][2];

            while(j < s)
            {
                edge &ed = edges[unchanged[j]];
                if(ed.wt >= car_wt) size_union(ed.u,ed.v) , j++;
                else break;
            }

            // Adding GOOD edges from the CHANGING edges
            vpii eds;
            for(auto &id : to_add[i])
            {
                edge &ed = edges[id];
                int u = find_par(ed.u);
                int v = find_par(ed.v);
                if(u != v) adj[u].clear(), adj[v].clear(), vis2[u] = vis2[v] = 0, eds.pb({u,v});
            }
            start = find_par(start);
            adj[start].clear() , vis2[start] = 0;
            
            for(auto &pr : eds) add_edge(pr.ff , pr.ss);
            int ans = 0;
            dfs(start , ans);
            answer[i] = ans;
        }
        rep(i,r-l+1) if(cur_q[i][0] == 2) pi(answer[i]);
    }
  return 0;
}
// ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Compilation message (stderr)

bridges.cpp: In function 'std::string uppercase(std::string)':
bridges.cpp:45:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   45 | #define loop(i,s,e) for (int (i)=(s);(i)<(e);++(i))
      |                              ^
bridges.cpp:50:18: note: in expansion of macro 'loop'
   50 | #define rep(i,n) loop(i,0,n)
      |                  ^~~~
bridges.cpp:151:3: note: in expansion of macro 'rep'
  151 |   rep(i,n) if (s[i] >= 'a' && s[i] <= 'z') s[i] = s[i] - 'a' + 'A';
      |   ^~~
bridges.cpp: In function 'std::string lowercase(std::string)':
bridges.cpp:45:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   45 | #define loop(i,s,e) for (int (i)=(s);(i)<(e);++(i))
      |                              ^
bridges.cpp:50:18: note: in expansion of macro 'loop'
   50 | #define rep(i,n) loop(i,0,n)
      |                  ^~~~
bridges.cpp:157:3: note: in expansion of macro 'rep'
  157 |   rep(i,n) if (s[i] >= 'A' && s[i] <= 'Z') s[i] = s[i] - 'A' + 'a';
      |   ^~~
bridges.cpp: In function 'void reset(int)':
bridges.cpp:46:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   46 | #define loope(i,s,e) for (int (i)=(s);(i)<=(e);++(i))
      |                               ^
bridges.cpp:51:19: note: in expansion of macro 'loope'
   51 | #define repn(i,n) loope(i,1,n)
      |                   ^~~~~
bridges.cpp:188:5: note: in expansion of macro 'repn'
  188 |     repn(i,n) size_[i] = 1;
      |     ^~~~
bridges.cpp:46:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   46 | #define loope(i,s,e) for (int (i)=(s);(i)<=(e);++(i))
      |                               ^
bridges.cpp:51:19: note: in expansion of macro 'loope'
   51 | #define repn(i,n) loope(i,1,n)
      |                   ^~~~~
bridges.cpp:189:5: note: in expansion of macro 'repn'
  189 |     repn(i,n) parent[i] = i;
      |     ^~~~
bridges.cpp: In function 'int main()':
bridges.cpp:46:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   46 | #define loope(i,s,e) for (int (i)=(s);(i)<=(e);++(i))
      |                               ^
bridges.cpp:51:19: note: in expansion of macro 'loope'
   51 | #define repn(i,n) loope(i,1,n)
      |                   ^~~~~
bridges.cpp:234:5: note: in expansion of macro 'repn'
  234 |     repn(i,m) edges[i].read();
      |     ^~~~
bridges.cpp:45:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   45 | #define loop(i,s,e) for (int (i)=(s);(i)<(e);++(i))
      |                              ^
bridges.cpp:50:18: note: in expansion of macro 'loop'
   50 | #define rep(i,n) loop(i,0,n)
      |                  ^~~~
bridges.cpp:248:9: note: in expansion of macro 'rep'
  248 |         rep(i,r-l+1)
      |         ^~~
bridges.cpp:45:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   45 | #define loop(i,s,e) for (int (i)=(s);(i)<(e);++(i))
      |                              ^
bridges.cpp:50:18: note: in expansion of macro 'loop'
   50 | #define rep(i,n) loop(i,0,n)
      |                  ^~~~
bridges.cpp:257:9: note: in expansion of macro 'rep'
  257 |         rep(i,r-l+1)
      |         ^~~
bridges.cpp:46:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   46 | #define loope(i,s,e) for (int (i)=(s);(i)<=(e);++(i))
      |                               ^
bridges.cpp:51:19: note: in expansion of macro 'loope'
   51 | #define repn(i,n) loope(i,1,n)
      |                   ^~~~~
bridges.cpp:276:9: note: in expansion of macro 'repn'
  276 |         repn(i,m) if(!change[i]) unchanged.pb(i);
      |         ^~~~
bridges.cpp:45:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   45 | #define loop(i,s,e) for (int (i)=(s);(i)<(e);++(i))
      |                              ^
bridges.cpp:50:18: note: in expansion of macro 'loop'
   50 | #define rep(i,n) loop(i,0,n)
      |                  ^~~~
bridges.cpp:312:9: note: in expansion of macro 'rep'
  312 |         rep(i,r-l+1) if(cur_q[i][0] == 2) pi(answer[i]);
      |         ^~~
bridges.cpp:12:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 | #define si2(x,y) scanf("%d %d",&x,&y)
      |                  ~~~~~^~~~~~~~~~~~~~~
bridges.cpp:81:30: note: in expansion of macro 'si2'
   81 | #define takei2(a,b) int a,b; si2(a,b)
      |                              ^~~
bridges.cpp:231:5: note: in expansion of macro 'takei2'
  231 |     takei2(n,m);
      |     ^~~~~~
bridges.cpp:11:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 | #define si(x) scanf("%d",&x)
      |               ~~~~~^~~~~~~~~
bridges.cpp:80:25: note: in expansion of macro 'si'
   80 | #define takei(a) int a; si(a)
      |                         ^~
bridges.cpp:241:5: note: in expansion of macro 'takei'
  241 |     takei(q);
      |     ^~~~~
bridges.cpp:11:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 | #define si(x) scanf("%d",&x)
      |               ~~~~~^~~~~~~~~
bridges.cpp:80:25: note: in expansion of macro 'si'
   80 | #define takei(a) int a; si(a)
      |                         ^~
bridges.cpp:250:13: note: in expansion of macro 'takei'
  250 |             takei(t);
      |             ^~~~~
bridges.cpp:12:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 | #define si2(x,y) scanf("%d %d",&x,&y)
      |                  ~~~~~^~~~~~~~~~~~~~~
bridges.cpp:81:30: note: in expansion of macro 'si2'
   81 | #define takei2(a,b) int a,b; si2(a,b)
      |                              ^~~
bridges.cpp:251:13: note: in expansion of macro 'takei2'
  251 |             takei2(id,wt);
      |             ^~~~~~
bridges.cpp: In member function 'void edge::read()':
bridges.cpp:77:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |     void read() {scanf("%d %d %d" , &u, &v, &wt);}
      |                  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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