Submission #295718

#	Time	Username	Problem	Language	Result	Execution time	Memory
295718		CaroLinda	Bridges (APIO19_bridges)	C++14	13 / 100	3077 ms	7800 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 ;

struct Edge
{
    int j , id ;
    Edge(int j = 0 , int id=0):j(j) , id(id) {}
};

int N , M , Q , cnt ;
int W[MAXM] ;
vector<Edge> adj[MAXN] ;
bool vis[MAXN] ;

void dfs(int x, int w)
{
    cnt++;
    vis[x] = true ;

    for(auto e : adj[x] )
    {
        if( vis[e.j] || W[ e.id ] < w ) continue ;
        dfs(e.j, w) ;
    }

}

int main()
{
    scanf("%d%d", &N , &M ) ;
    for(int i = 1 , u , v ; i <= M ; i++ )
    {
        scanf("%d%d%d", &u, &v, &W[i] ) ;

        adj[u].pb( Edge(v,i) ) ;
        adj[v].pb( Edge(u,i) ) ;

    }

    scanf("%d", &Q ) ;

    for(int i = 1 ,t, a , b ; i <= Q ; i++ )
    {
        scanf("%d%d%d", &t, &a, &b ) ;

        if(t == 1)
        {
            W[a] = b ;
            continue ;
        }

        lp(j,1,N+1) vis[j] = false ;
        cnt = 0 ;
        dfs(a,b) ;

        printf("%d\n" , cnt ) ;

    }


}

/*
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: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[i] ) ;
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:66:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   66 |     scanf("%d", &Q ) ;
      |     ~~~~~^~~~~~~~~~~
bridges.cpp:70:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   70 |         scanf("%d%d%d", &t, &a, &b ) ;
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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