Submission #227528

#	Time	Username	Problem	Language	Result	Execution time	Memory
227528		Shafin666	Senior Postmen (BOI14_postmen)	C++14	55 / 100	638 ms	65428 KiB

postmen

#include <bits/stdc++.h>
#define pb push_back
#define pii pair<ll, ll>
#define nyan "(=^･ω･^=)"
#define read_input         freopen("in.txt","r", stdin)
#define print_output       freopen("out.txt","w", stdout)
typedef long long ll;
typedef long double ld;
using namespace std;

const int maxn = 5e5+10;
vector<int> adj[maxn], ans[maxn];
int del[maxn], l[maxn], r[maxn];
int pre[maxn];

vector<int> find(int u) {
    vector<int> stack, curr(maxn), res;

    stack.pb(u) ;
    while(!stack.empty()) {
        u = stack.back();
        stack.pop_back();

        while(curr[u] < (int) adj[u].size() - 1) {
            while(del[adj[u][curr[u]]]) curr[u]++;
            int e = adj[u][curr[u]++];
            if(e == 0) break;

            stack.pb(u);

            u = l[e] ^ r[e] ^ u;
            del[e] = 1;
        }
        res.pb(u);
    }
    reverse(res.begin(), res.end());
    return res;
}

int main() 
{
    int n, m;
    scanf("%d %d", &n, &m);

    for(int i = 1; i <= m; i++) {
        scanf("%d %d", &l[i], &r[i]);

        adj[l[i]].pb(i);
        adj[r[i]].pb(i);
    }
    for(int i = 1; i <= n; i++) adj[i].pb(0);

    vector<int> euler = find(1);

    stack<int> s;
    memset(pre, -1, sizeof pre);

    int j = 0, cnt = -1;
    while(j < (int) euler.size()) {
        s.push(euler[j]);

        if(pre[euler[j]] != -1) {
            // ans[++cnt].pb(euler[j]);
            cnt++; s.pop();

            while(1) {
                int here = s.top();
                ans[cnt].pb(here);
                
                if(pre[here] == pre[euler[j]]) break;
                pre[here] = -1;
                s.pop();
            }
        }
        else pre[euler[j]] = j;
        j++;
    }

    cnt++;
    while(!s.empty()) ans[cnt].pb(s.top()), s.pop();

    for(int i = 0; i < cnt; i++) {
        for(auto it : ans[i]) printf("%d ", it);
        printf("\n");
    }

    return 0;   
}

Compilation message (stderr)

postmen.cpp: In function 'int main()':
postmen.cpp:43: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:46:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &l[i], &r[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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