Submission #31563

#	Time	Username	Problem	Language	Result	Execution time	Memory
31563		minhtung0404	Senior Postmen (BOI14_postmen)	C++14	55 / 100	541 ms	51664 KiB

postmen

#include<bits/stdc++.h>
const int N = 5e5 + 5;
using namespace std;

typedef pair <int, int> ii;
vector <ii> adj[N];
vector <int> mv[N];

int n, m, a, b;
int ms[2][N], cnt[2], mi[N], ma[N];
bool check[N], edge[N];

void dfs(){
    ms[0][++cnt[0]] = 1;
    while(cnt[0]){
        int u = ms[0][cnt[0]];
        while(mi[u] < ma[u] && edge[adj[u][mi[u]].second]) mi[u]++;
        if (mi[u] < ma[u]) {
            ms[0][++cnt[0]] = adj[u][mi[u]].first;
            edge[adj[u][mi[u]].second] = 1;
            mi[u]++;
        }
        else{
            if (check[u]){
                while(ms[1][cnt[1]] != u) {
                    printf("%d ", ms[1][cnt[1]]);
                    check[ms[1][cnt[1]]] = 0;
                    cnt[1]--;
                }
                printf ("%d\n", u);
                cnt[1]--;
                check[u] = 0;
            }
            check[u] = 1;
            ms[1][++cnt[1]] = u;
            cnt[0]--;
        }
    }
}

int main(){
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++){
        scanf("%d%d", &a, &b);
        adj[a].push_back(ii(b, i));
        adj[b].push_back(ii(a, i));
    }
    for (int i = 1; i <= n; i++){
        ma[i] = adj[i].size();
    }
    dfs();
}

Compilation message (stderr)

postmen.cpp: In function 'int main()':
postmen.cpp:42:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~
postmen.cpp:44:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &a, &b);
         ~~~~~^~~~~~~~~~~~~~~~

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