Submission #262396

#	Time	Username	Problem	Language	Result	Execution time	Memory
262396		CaroLinda	Duathlon (APIO18_duathlon)	C++14	16 / 100	253 ms	512 KiB

count_triplets

#include <bits/stdc++.h>

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

const int MAXN = 110 ;
const int MAXM = 510;
const int inf = 1e9+7;

using namespace std ;

int N , M , resp , T , MM ;
int flow[MAXM] , cap[MAXM] , cont[MAXM] ;
vector<int> pilha ;
vector<pii> adj[MAXN*2] ;
bool vis[MAXN] ;
bool flag ;

int get(int x) { return cap[x] - flow[x] ; }

int bfs(int x )
{
    vis[x] = true ;

    if(x == T) return inf ;

    for(auto e : adj[x] )
    {

        if( get(e.ss) <= 0 || vis[e.ff] ) continue ;

        //cout << x << " " << get(e.ss) << " " << e.ss << " " << e.ff << endl ;

        int t = min(bfs(e.ff), get(e.ss) ) ;

        if(t <= 0) continue ;

        pilha.pb( e.ss ) ;
        return t ;

    }

    return 0 ;

}

void add_edge(int x, int y , int c)
{
    cap[++M] = c ;
    flow[M] = 0 ;
    adj[x].pb( mk(y,M) ) ;
    cont[M] = M+1 ;
    M++ ;
    cont[M] = M-1 ;
    flow[M] = 0 ;
    adj[y].pb( mk(x, M) ) ;
}

int test(int a, int b, int c )
{
    lp(i,1,M+1) flow[i] = 0 ;

    T = 2*N+1 ;

    add_edge(b+N, T, 1) ;
    add_edge(c+N , T , 1  );
    cap[ adj[a][0].ss ]++ ;


    int F = 0  , f = 0 ;

    lp(i,1,T+1) vis[i] = false ;
    pilha.clear() ;

    while( f = bfs(a) )
    {
        F += f ;

        lp(i,1,T+1) vis[i] = false ;

        for(auto e : pilha )
        {
            flow[e] += f ;
            flow[ cont[e] ] -= f ;
        }

        pilha.clear() ;

    }

    adj[b+N].pop_back() ;
    adj[T].pop_back() ;
    adj[T].pop_back() ;
    adj[c+N].pop_back() ;
    M -= 4 ;
    cap[ adj[a][0].ss ]-- ;


    return F >= 2 ;

}

int main()
{

    scanf("%d%d", &N , &MM ) ;

    lp(i,1,N+1) add_edge(i, i+N, 1) ;

    for(int i = 1 , u , v ; i <= MM ; i++ )
    {
        scanf("%d%d", &u, &v ) ;
        add_edge(u+N, v, 1 ) ;
        add_edge( v+N , u , 1 ) ;
    }



    for(int i = 1 ; i <= N ; i++ )
        for(int j = 1 ; j <= N ; j++ )
            for(int g = j+1 ; g <= N ; g++ )
                if( i != j && i != g )
                    if( test(i,j,g) )
                    {
                        resp += 2 ;
                        debug("Deu bom em %d %d %d\n" , i, j , g ) ;
                    }

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

}

Compilation message (stderr)

count_triplets.cpp: In function 'int test(int, int, int)':
count_triplets.cpp:83:14: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   83 |     while( f = bfs(a) )
      |            ~~^~~~~~~~
count_triplets.cpp: In function 'int main()':
count_triplets.cpp:134:31: warning: left operand of comma operator has no effect [-Wunused-value]
  134 |                         debug("Deu bom em %d %d %d\n" , i, j , g ) ;
      |                               ^~~~~~~~~~~~~~~~~~~~~~~
count_triplets.cpp:134:60: warning: right operand of comma operator has no effect [-Wunused-value]
  134 |                         debug("Deu bom em %d %d %d\n" , i, j , g ) ;
      |                                                            ^
count_triplets.cpp:134:64: warning: right operand of comma operator has no effect [-Wunused-value]
  134 |                         debug("Deu bom em %d %d %d\n" , i, j , g ) ;
      |                                                                ^
count_triplets.cpp:114:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  114 |     scanf("%d%d", &N , &MM ) ;
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
count_triplets.cpp:120:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  120 |         scanf("%d%d", &u, &v ) ;
      |         ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 11 / 11
• Subtask 3: 0 / 8
• Subtask 4: 0 / 10
• Subtask 5: 0 / 13
• Subtask 6: 0 / 15
• Subtask 7: 0 / 20
• Subtask 8: 0 / 8
• Subtask 9: 0 / 10