Submission #107752

#	Time	Username	Problem	Language	Result	Execution time	Memory
107752		patrikpavic2	Senior Postmen (BOI14_postmen)	C++17	100 / 100	320 ms	44800 KiB

postmen

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <vector>

#define X first
#define Y second
#define PB push_back

using namespace std;

typedef pair < int, int > pii;
typedef vector < int > vi;

const int N = 5e5 + 5;

int bio[N], n, m, nod[N],ind[N], rek[N], cur;
vector < pii > v[N];
int tura[N], st[N], tr, ss, v1[N], v2[N];


inline bool is( const char &c ) { return c >= '0' && c <= '9'; }

inline int read_int( ) {
    int num;
    char c;
    while( !is( c = getchar_unlocked( ) ) );
    num = c - '0';
    while( is( c = getchar_unlocked( ) ) ) num = num * 10 + c - '0';
    return num;
}

inline void euler(){
    rek[cur++] = 1;
    for(;cur;){
        int x = rek[cur - 1];
        for(;ind[x] < v[x].size() && bio[v[x][ind[x]].Y];++ind[x]);
        if(ind[x] == v[x].size()) --cur, tura[tr++] = x;
        for(;ind[x] < v[x].size();++ind[x]){
            if(bio[v[x][ind[x]].Y]) continue;
            bio[v[x][ind[x]].Y] = 1;
            int nxt = v[x][ind[x]].X;
            rek[cur++] = nxt;
            break;
        }

    }
}

inline void rastavi(){
    memset(bio, 0, sizeof(bio));
    for(int i = 0;i < tr;++i){
        if(bio[tura[i]]){
            while(st[ss - 1] != tura[i]){
                printf("%d ", st[ss - 1]);
                bio[st[ss - 1]]--;
                --ss;
            }
            --ss;
            --bio[tura[i]];
            printf("%d\n", tura[i]);
        }
        st[ss++] = tura[i];
        ++bio[tura[i]];
    }
}

int main(){
    n = read_int(); m = read_int();
    for(int i = 0;i < m;++i){
        v1[i] = read_int();
        v2[i] = read_int();
        ind[v1[i]]++, ind[v2[i]]++;
    }
    for(int i = 1;i <= n;i++){
        v[i].resize(ind[i]);
        ind[i] = 0;
    }
    for(int i = 0;i < m;i++){
        v[v1[i]][ind[v1[i]]++].X = v2[i];
        v[v1[i]][ind[v1[i]] - 1].Y = i;
        v[v2[i]][ind[v2[i]]++].X = v1[i];
        v[v2[i]][ind[v2[i]] - 1].Y = i;
    }
    memset(ind, 0, sizeof(ind));
    euler();
    rastavi();
    return 0;
}

Compilation message (stderr)

postmen.cpp: In function 'void euler()':
postmen.cpp:37:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(;ind[x] < v[x].size() && bio[v[x][ind[x]].Y];++ind[x]);
              ~~~~~~~^~~~~~~~~~~~~
postmen.cpp:38:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(ind[x] == v[x].size()) --cur, tura[tr++] = x;
            ~~~~~~~^~~~~~~~~~~~~~
postmen.cpp:39:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(;ind[x] < v[x].size();++ind[x]){
              ~~~~~~~^~~~~~~~~~~~~

• Subtask 1: 38 / 38
• Subtask 2: 17 / 17
• Subtask 3: 45 / 45