Submission #130365

#	Time	Username	Problem	Language	Result	Execution time	Memory
130365		OptxPrime	Untitled (POI11_smi)	C++11	60 / 100	3026 ms	67924 KiB

Main

#include <iostream>
#include <cmath>
#include<vector>
#include <algorithm>
#include <utility>
#include<stack>
#include<queue>
#include<map>
#include <fstream>
#include<set>

using namespace std;

#define pb push_back
#define mp make_pair
#define ll long long
//#define maxn 100005

    struct edge{
        int node, id;
        edge(){}
        edge( int node, int id ) :node(node), id(id) {}
    };

        vector<vector<edge>> adjl;
        vector<vector<int>> res;
        vector<edge> elist;
        int n,m;
        stack<edge>s;
        bool is[100010];
       // bool eis[100010];
       map<int,bool> eis;
        int step[100010];
    void dfs( int x,int parent )
    {
            if( is[x] ){    ///ciklus
                   // cout << " ha " <<s.empty() << endl;
                vector<int> tmp;
                tmp.pb(x);
                eis[ s.top().id ]=true;
                is[ s.top().node ]=false; /// opet stavimo na false
                s.pop();    /// za gornji element koji je x
                while( !s.empty() && s.top().node!=x ){     /// dok OPET ne dodjemo do x, dakle drugi put
                    edge e =s.top();
                    tmp.pb( e.node );
                    eis[e.id]=true;
                    is[e.node]=false; /// vratimo node kao prije jer ih opet mozemo koristit u drugim ciklusima
                    s.pop();
                }
              //  cout << " iziso " <<endl;
            tmp.pb(x);
            res.pb(tmp);
            return;
            }
            is[x]=true;
            for( auto v:adjl[x] ){
                 //   cout << " wtf " <<endl;
                    if( v.node == parent ) continue;
                if( !eis[v.id] ){
                        s.push( v );
                    dfs( v.node, x );
                    return; /// samo u jednom smjeru idemo
                }
            }
    }

    int main()
    {
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);

        /// kako kucat podjelu na cikluse
        /// smislit neki bolji nacin, ovo dosad lose
        /// ideja: cim naletis na prvi ciklus, skroz terminate program, i opet pozivas dfs. pamtis samo edgeve koje si uzeo prolazeci kroz ciklus

        int a,b,p,t;
        cin>>n>>m;
        adjl.resize(n);
        for( int i=0;i<m;i++ ){
            cin>>a>>b>>p>>t;
            if( p!=t ){
                a--;
                b--;
                step[a]++;
                step[b]++;
                adjl[a].pb( edge(b,i) );
                adjl[b].pb( edge( a,i ) );
                elist.pb(edge( a,i )); /// cudno cuvamo edge al eto
            }
        }

         for( int i=0;i<n;i++ ){
                if( step[i]%2==1 ){
                    cout<<"NIE"<<endl;
                    return 0;
                }
            }
        for( int i=0;i<m;i++ ){

            while( !eis[ elist[i].id ] ){        ///sve dok ne krene putem edga koji je tu, nek ponovo poziva odatle dfs
               // cout << " kolko " << elist[i].id << " " << elist[i].node  <<endl;
               while( !s.empty() ){
                 //   cout << " aaa " <<endl;
                 is[ s.top().node ]=false;
                s.pop();
               }
               s.push( elist[i] );
                dfs( elist[i].node, elist[i].node ); ///prvi put da pozivam ovako dfs po edgevima
            }
        }

        cout <<res.size()<<endl;
        for( int i=0;i<res.size();i++ ){
                cout <<res[i].size()-1 << " ";
            for( int j=0;j<res[i].size();j++ )
                cout<<res[i][j]+1 << " ";
            cout<<endl;
        }


      return 0;
    }

Compilation message (stderr)

smi.cpp: In function 'int main()':
smi.cpp:113:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for( int i=0;i<res.size();i++ ){
                      ~^~~~~~~~~~~
smi.cpp:115:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for( int j=0;j<res[i].size();j++ )
                          ~^~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10