Submission #295714

#	Time	Username	Problem	Language	Result	Execution time	Memory
295714		CaroLinda	Bridges (APIO19_bridges)	C++14	14 / 100	126 ms	7908 KiB

bridges

//Subtask 4

#include <bits/stdc++.h>

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
#pragma GCC optimization ("O2")

#define lp(i,a,b) for(int i = a; i < b; i++)
#define pb push_back
#define sz(x) (int)(x.size())
#define all(x) x.begin(),x.end()
#define debug printf
#define tiii tuple<int,int,int>
#define mkt make_tuple
#define pii pair<int,int>
#define mk make_pair
#define ll long long
#define ff first
#define ss second


const int MAXN = 5e4+10 ;
const int MAXM = 1e5+10 ;
const int inf = 1e9+7 ;

using namespace std ;

int N , M , Q ;
int pai[MAXN] , tam[MAXN] , ans[MAXM] ;
vector<tiii> edge ;

int find(int x)
{
    if(x == pai[x]) return x ;
    return pai[x] = find(pai[x]) ;
}

void join(int x, int y)
{
    x = find(x);
    y = find(y) ;

    if(x == y) return ;

    if(rand() % 2 ) swap(x,y) ;

    pai[x] = y;
    tam[y] += tam[x] ;

}

int main()
{
    scanf("%d%d", &N , &M ) ;
    for(int i = 1 , u , v , w ; i <= M ; i++ )
    {
        scanf("%d%d%d", &u, &v, &w ) ;
        edge.pb(mkt(w,u,v)) ;
    }

    scanf("%d", &Q ) ;
    for(int i = 1 , u ,v , t ; i <= Q ; i++ )
    {
        scanf("%d%d%d", &t , &u, &v ) ;
        assert(t == 2) ;
        edge.pb( mkt(v, -u, i) ) ;
    }

    sort(all(edge)) ;
    reverse(all(edge)) ;

    lp(i,1,N+1)
    {
        pai[i] = i ;
        tam[i] = 1 ;
    }

    for(auto tup : edge )
    {
        int a = get<0>(tup);
        int b= get<1>(tup) ;
        int c = get<2>(tup) ;

        if( b > 0 ) join(b,c) ;
        else ans[c] = tam[ find(-b) ] ;

    }

    lp(i,1,Q+1) printf("%d\n" , ans[i]) ;

}

/*
3 4
1 2 5
2 3 2
3 1 4
2 3 8
3
2 1 5
2 2 5
2 3 2
*/

Compilation message (stderr)

bridges.cpp:7: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    7 | #pragma GCC optimization ("unroll-loops")
      | 
bridges.cpp:8: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    8 | #pragma GCC optimization ("O2")
      | 
bridges.cpp: In function 'int main()':
bridges.cpp:82:13: warning: unused variable 'a' [-Wunused-variable]
   82 |         int a = get<0>(tup);
      |             ^
bridges.cpp:56:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   56 |     scanf("%d%d", &N , &M ) ;
      |     ~~~~~^~~~~~~~~~~~~~~~~~
bridges.cpp:59:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   59 |         scanf("%d%d%d", &u, &v, &w ) ;
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:63:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   63 |     scanf("%d", &Q ) ;
      |     ~~~~~^~~~~~~~~~~
bridges.cpp:66:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   66 |         scanf("%d%d%d", &t , &u, &v ) ;
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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