Cod sursa(job #2278964)

Utilizator triscacezarTrisca Vicol Cezar triscacezar Data 8 noiembrie 2018 19:20:05
Problema Ciclu Eulerian Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.02 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f("domino.in");
ofstream g("domino.out");

int n,i,x,y,ok[20],last[20];
stack<int> St;
vector<pair<int,int> > v[20],drumuri[20][20];
vector<int> drum;
bitset<50010> used;

void euler(int nod)
{
    for(auto it:v[nod])
        if(!used[it.second])
        {
            used[it.second]=1;
            euler(it.first);
        }
    drum.push_back(nod);
}

int main()
{
    f>>n;
    for(i=1;i<=n;i++)
    {
        f>>x>>y;
        v[x].push_back({y,i});
        v[y].push_back({x,i});
        ok[x]++;ok[y]++;
        if(x<=y)
            drumuri[x][y].push_back({i,0});
        else
            drumuri[y][x].push_back({i,1});
    }
    int cnt=0;
    for(i=0;i<=9;i++)
        if(ok[i]&1)
            cnt++;
    if((cnt!=0)&&(cnt!=2))
    {
        g<<0;
        return 0;
    }
    if(cnt==0)
        for(i=0;i<=9;i++)
            if(ok[i])
            {
                St.push(i);
                break;
            }
            else;
    else
        for(i=0;i<=9;i++)
            if(ok[i]&1)
            {
                St.push(i);
                break;
            }
    while(St.size())
    {
        x=St.top();
        for(;last[x]<v[x].size();last[x]++)
            if(!used[v[x][last[x]].second])
            {
                used[v[x][last[x]].second]=1;
                St.push(v[x][last[x]].first);
                break;
            }
        if(last[x]==v[x].size())
        {
            drum.push_back(x);
            St.pop();
        }
    }
    if(drum.size()!=n+1)
    {
        g<<0;
        return 0;
    }
    g<<1<<'\n';
    for(i=0;i<drum.size()-1;i++)
    {
        int frst=min(drum[i],drum[i+1]),scnd=max(drum[i],drum[i+1]);
        pair<int,int> aux=drumuri[frst][scnd].back();
        drumuri[frst][scnd].pop_back();
        if(frst==drum[i])
            g<<aux.first<<' '<<aux.second<<'\n';
        else
            g<<aux.first<<' '<<1-aux.second<<'\n';
    }
    return 0;
}