제출 #130466

#제출 시각아이디문제언어결과실행 시간메모리
130466OptxPrime무제 (POI11_smi)C++11
10 / 100
946 ms75272 KiB
#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,int start ) { if( is[x] ){ ///ciklus 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); dfs( start, start, start ); } is[x]=true; for( auto v:adjl[x] ){ // cout << " wtf " <<endl; if( v.node == parent ) continue; if( !eis[v.id] ){ s.push( v ); eis[v.id]=true; dfs( v.node, x, start ); return; /// samo u jednom smjeru idemo } } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); 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, 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; }

컴파일 시 표준 에러 (stderr) 메시지

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