Submission #561490

#	Time	Username	Problem	Language	Result	Execution time	Memory
561490		CaroLinda	Parachute rings (IOI12_rings)	C++14	Compilation error	0 ms	0 KiB

rings

#include <bits/stdc++.h>

#define pii pair<int,int>
#define mk make_pair
#define lp(i,a,b) for(int i = a ; i < b ; i++)
#define ff first
#define ss second
#define pb push_back
#define ll long long
#define debug printf

const int MAXN = 1e6+10 ;

using namespace std ;


struct Graph
{

    int ans , N ;
    int pai[MAXN] , deg[MAXN] ;
    vector<int> adj[MAXN] ;
    bool marc[MAXN] , can_be[MAXN] , exist[MAXN] ;
    bool operational ;

    Graph()
    {
        N = MAXN - 5 ;
        lp(i,1,N+1)
        {
            deg[i] = 0 ;
            marc[i] = false ;
            can_be[i] = true ;
            pai[i] = i ;
            exist[i] = true ;
        }
        operational = true ;
        ans = N ;
    }

    int get_return() { return operational ; }

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

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

        if( x == y ) return false ;

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

        pai[x] = y ;

        return true ;

    }

    bool dfs(int x, int desired )
    {
        marc[x] = true ;
        bool can = ( x == desired ) ;

        for(int i : adj[x] )
            if( !marc[i] ) can |= dfs(i, desired) ;

        if(can) ans += can_be[x] ;
        else can_be[x] = false ;

        return can ;

    }

    void make_link(int A, int B)
    {

        if( !exist[A] || !exist[B] ) return ;

        if( !join(A,B) || max( ++deg[A] , ++deg[B] ) >= 3 ) operational = false ;

        adj[A].pb(B) ;
        adj[B].pb(A) ;

    }


} ;

int N , L ;
bool forest_ok ;
Graph graph[5] ;
vector<pii> edges ;

inline void make_partition(int center)
{

    vector<int> List ;

    List.pb(center) ;
    for(int i : graph[0].adj[center] ) List.pb( i ) ;

    for(int i = 0 , idx = 1 ; i < List.size() ; i++ , idx ++ )
    {
        graph[idx].exist[ List[i] ] = false ;
        for(auto p : edges ) graph[idx].make_link(p.ff, p.ss) ;
    }
    forest_ok = true ;
    graph[0].ans = 0 ;
    lp(i,1,5) graph[0].ans += graph[i].operational ;
}

int main()
{
    scanf("%d%d", &N , &L ) ;
    graph[0].ans = N ;

    while( L-- )
    {
        int A , B ;

        scanf("%d", &A ) ;

        if( A == -1 )
        {
            printf("%d\n",  graph[0].ans ) ;
            continue ;
        }

        scanf("%d", &B ) ;
        A++ ; B++ ;

        if( graph[0].ans == 0 ) continue ;

        edges.pb( mk(A,B) ) ;

        if( !forest_ok )
        {
            graph[0].deg[A] ++ ;
            graph[0].deg[B] ++ ;

            if( graph[0].deg[A] < graph[0].deg[B] ) swap(A,B) ;

            if( graph[0].deg[A] == 3 )
            {
                graph[0].adj[A].pb(B) ;
                graph[0].adj[B].pb(A) ;

                make_partition(A) ;
                continue ;
            }

            if( !graph[0].join(A,B) )
            {
                graph[0].ans = 0 ;
                lp(i,1,N+1) graph[0].marc[i] = false ;
                graph[0].dfs(A, B) ;
                lp(i,1,N+1)
                    if( !graph[0].marc[i] )
                        graph[0].dfs(i,A) ;
            }

            graph[0].adj[A].pb(B) ;
            graph[0].adj[B].pb(A) ;
            continue;
        }

        for(int i = 1 ; i <= 4 ; i++ )
        {
            graph[0].ans -= graph[i].operational ;
            graph[i].make_link(A,B) ;
            graph[0].ans += graph[i].operational ;
        }

    }
}

Compilation message (stderr)

rings.cpp: In function 'void make_partition(int)':
rings.cpp:107:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |     for(int i = 0 , idx = 1 ; i < List.size() ; i++ , idx ++ )
      |                               ~~^~~~~~~~~~~~~
rings.cpp: In function 'int main()':
rings.cpp:119:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  119 |     scanf("%d%d", &N , &L ) ;
      |     ~~~~~^~~~~~~~~~~~~~~~~~
rings.cpp:126:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  126 |         scanf("%d", &A ) ;
      |         ~~~~~^~~~~~~~~~~
rings.cpp:134:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  134 |         scanf("%d", &B ) ;
      |         ~~~~~^~~~~~~~~~~
/usr/bin/ld: /tmp/ccEJHDqO.o: in function `main':
rings.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cctp2pLO.o:grader.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/cctp2pLO.o: in function `main':
grader.cpp:(.text.startup+0x88): undefined reference to `Init(int)'
/usr/bin/ld: grader.cpp:(.text.startup+0xca): undefined reference to `Link(int, int)'
/usr/bin/ld: grader.cpp:(.text.startup+0xed): undefined reference to `CountCritical()'
collect2: error: ld returned 1 exit status