Submission #683058

#	Time	Username	Problem	Language	Result	Execution time	Memory
683058		Vladth11	Senior Postmen (BOI14_postmen)	C++14	100 / 100	453 ms	71044 KiB

postmen

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")

#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "

using namespace std;
typedef pair <int, int> pii;
typedef long long ll;

const int NMAX = 500001;
const int VMAX = 41;
const int INF = 1e9;
const int MOD = 1000000009;
const int BLOCK = 318;
const int base = 31;
const int nrbits = 21;

struct muchie {
    int ambele;
    int viz;
} edges[NMAX];

vector <int> v[NMAX];

vector <int> euler;

void DFS(int node) {
    while(v[node].size()) {
        int ind = v[node].back();
        v[node].pop_back();
        if(edges[ind].viz == 1) continue;
        edges[ind].viz = 1;
        int vecin = (edges[ind].ambele ^ node);
        DFS(vecin);
    }
    euler.push_back(node);
}

vector <int> stiva;
int f[NMAX];

int main() {
#ifdef HOME
    ifstream cin(".in");
    ofstream cout(".out");
#endif // HOME
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m, i;
    cin >> n >> m;
    for(i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;
        edges[i].ambele = (x ^ y);
        edges[i].viz = 0;
        v[x].push_back(i);
        v[y].push_back(i);
    }
    DFS(1);
    for(auto x : euler) {
        if(f[x]) {
            while(stiva.back() != x) {
                cout << stiva.back() << " ";
                f[stiva.back()]--;
                stiva.pop_back();
            }
            cout << stiva.back() << " ";
            f[stiva.back()]--;
            stiva.pop_back();
            cout << "\n";
        }
        stiva.push_back(x);
        f[x]++;
    }
    return 0;
}

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