Submission #130486

#	Time	Username	Problem	Language	Result	Execution time	Memory
130486		OptxPrime	Untitled (POI11_smi)	C++11	80 / 100	3037 ms	202280 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;
        int is[100010];
        int odakle[100010];
       // bool eis[100010];
       map<int,bool> eis;
        int step[100010];
    void dfs( int x,int parent )
    {
        is[x]++;
            if( is[x]==2 ){    ///ciklus

                vector<int> tmp;
                tmp.pb(x);
                is[ s.top().node ]--; /// 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 );
                    is[e.node]--; /// vratimo node kao prije jer ih opet mozemo koristit u drugim ciklusima
                    s.pop();
                }
            tmp.pb(x);
            res.pb(tmp);
            }
            for( int i=odakle[x];i<adjl[x].size();i++ ){

                    edge v=adjl[x][i];
                    odakle[x]++;
                if( !eis[v.id] ){
                        s.push( v );
                        eis[v.id]=true;
                        dfs( v.node, x );
                        return; /// samo u jednom smjeru idemo (bio sam upravu, jedan smjer)
                }
            }
    }

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


        int a,b,p,t;
        cin>>n>>m;
        for(int i=0;i<n;i++)odakle[i]=0;
        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 'void dfs(int, int)':
smi.cpp:53:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for( int i=odakle[x];i<adjl[x].size();i++ ){
                                  ~^~~~~~~~~~~~~~~
smi.cpp: In function 'int main()':
smi.cpp:110:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for( int i=0;i<res.size();i++ ){
                      ~^~~~~~~~~~~
smi.cpp:112: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: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 0 / 10