| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 130487 |
2019-07-15T10:50:39 Z |
OptxPrime |
Garbage (POI11_smi) |
C++11 |
|
2906 ms |
202072 KB |
#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
/// prolazi za 80, na jednom subtask MLE na drugom TLE al dosta i ovo
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] ){
step[v.node]--;
step[x]--;
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;
}
}
/// puno edgeva, zato je tle a garant imle zbog elist
/* 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
}
}*/
for( int i=0;i<n;i++ ){
if( step[i] > 0 ) dfs(i,i );
}
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
smi.cpp: In function 'void dfs(int, int)':
smi.cpp:55: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:118:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for( int i=0;i<res.size();i++ ){
~^~~~~~~~~~~
smi.cpp:120:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for( int j=0;j<res[i].size();j++ )
~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
632 KB |
Output is correct |
| 2 |
Correct |
3 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
1208 KB |
Output is correct |
| 2 |
Correct |
4 ms |
504 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
1016 KB |
Output is correct |
| 2 |
Correct |
4 ms |
504 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
2296 KB |
Output is correct |
| 2 |
Correct |
6 ms |
632 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
200 ms |
19392 KB |
Output is correct |
| 2 |
Correct |
2591 ms |
200024 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1453 ms |
96268 KB |
Output is correct |
| 2 |
Correct |
2632 ms |
183288 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2356 ms |
146588 KB |
Output is correct |
| 2 |
Correct |
2725 ms |
190672 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2906 ms |
169044 KB |
Output is correct |
| 2 |
Correct |
2739 ms |
202072 KB |
Output is correct |
