oj.uz

Submission #881090

# Submission time Handle Problem Language Result Execution time Memory
881090 2023-11-30T14:46:05 Z Requiem Senior Postmen (BOI14_postmen) C++17
38 / 100
 500 ms 27476 KB 
#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#define MOD 1000000007
#define INF 1e18
#define fi first
#define se second
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define sz(a) ((int)(a).size())
#define endl '\n'
#define pi 3.14159265359
#define TASKNAME "postmen"
template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
using namespace std;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;
const int MAXN = 5e5 + 9;
vector<int> g[MAXN];
int n,m,deg[MAXN];
bool used[MAXN];
ii edge[MAXN];
list<int> euler_circuit(int u){
    list<int> ans;
    int v;
    ans.pb(u);
    while(!g[u].empty()){
        int id = g[u].back();
        g[u].pop_back();
        if (used[id]) continue;
        v = edge[id].fi + edge[id].se - u;
        used[id] = true;
        u = v;
        ans.pb(u);
    }
    auto it = ans.begin();
    it++;
    for(; it != ans.end(); it++){
        list<int> vert = euler_circuit((*it));
        vert.pop_front();
        ans.splice(next(it),vert);
    }

    return ans;
}
bool inqueue[MAXN];
main()
{
    fast;
    if (fopen(TASKNAME".inp","r")){
        freopen(TASKNAME".inp","r",stdin);
        freopen(TASKNAME".out","w",stdout);
    }
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>edge[i].fi>>edge[i].se;
        g[edge[i].fi].pb(i);
        g[edge[i].se].pb(i);
        deg[edge[i].fi]++;
        deg[edge[i].se]++;
    }

    memset(inqueue,false,sizeof(inqueue));
//    for(auto x: ans){
//        cout<<x<<' ';
//    }
//    cout<<endl;

    for(int i=1;i<=n;i++){
        if (deg[i]&1) {
            cout<<"IMPOSSIBLE"<<endl;
            return 0;
        }
    }
    memset(used,false,sizeof(used));
    list<int> ans = euler_circuit(1);
//    for(auto x: ans){
//        cout<<x<<' ';
//    }
//    cout<<endl;
    stack<int> st;
    for(auto x: ans){
        if (!inqueue[x]){
            inqueue[x] = true;
            st.push(x);
        }
        else{
            cout<<x<<' ';
            while(!st.empty() and st.top() != x){
                cout<<st.top()<<' ';
                inqueue[st.top()] = false;
                st.pop();
            }
            cout<<endl;
        }
    }
    cout<<endl;
}

Compilation message

postmen.cpp:50:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   50 | main()
      | ^~~~
postmen.cpp: In function 'int main()':
postmen.cpp:59:13: warning: unused variable 'u' [-Wunused-variable]
   59 |         int u,v;
      |             ^
postmen.cpp:59:15: warning: unused variable 'v' [-Wunused-variable]
   59 |         int u,v;
      |               ^
postmen.cpp:54:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |         freopen(TASKNAME".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
postmen.cpp:55:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |         freopen(TASKNAME".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 18524 KB Output is correct
2 Correct 4 ms 18524 KB Output is correct
3 Correct 4 ms 18520 KB Output is correct
4 Correct 5 ms 18780 KB Output is correct
5 Correct 4 ms 18780 KB Output is correct
6 Correct 6 ms 18848 KB Output is correct
7 Correct 8 ms 19804 KB Output is correct
8 Correct 5 ms 18776 KB Output is correct
9 Correct 28 ms 24592 KB Output is correct
10 Correct 5 ms 18780 KB Output is correct
11 Correct 6 ms 18780 KB Output is correct
12 Correct 31 ms 25096 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 18524 KB Output is correct
2 Correct 4 ms 18524 KB Output is correct
3 Correct 4 ms 18760 KB Output is correct
4 Correct 5 ms 18780 KB Output is correct
5 Correct 5 ms 18776 KB Output is correct
6 Correct 5 ms 19036 KB Output is correct
7 Correct 8 ms 19800 KB Output is correct
8 Correct 5 ms 18780 KB Output is correct
9 Correct 29 ms 24708 KB Output is correct
10 Correct 5 ms 18780 KB Output is correct
11 Correct 5 ms 18780 KB Output is correct
12 Correct 39 ms 25236 KB Output is correct
13 Correct 46 ms 27472 KB Output is correct
14 Execution timed out 1083 ms 26448 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 18520 KB Output is correct
2 Correct 4 ms 18524 KB Output is correct
3 Correct 4 ms 18520 KB Output is correct
4 Correct 5 ms 18960 KB Output is correct
5 Correct 4 ms 18776 KB Output is correct
6 Correct 5 ms 19036 KB Output is correct
7 Correct 8 ms 19804 KB Output is correct
8 Correct 5 ms 18844 KB Output is correct
9 Correct 28 ms 24632 KB Output is correct
10 Correct 5 ms 18776 KB Output is correct
11 Correct 5 ms 18780 KB Output is correct
12 Correct 31 ms 25108 KB Output is correct
13 Correct 42 ms 27476 KB Output is correct
14 Execution timed out 1055 ms 26452 KB Time limit exceeded
15 Halted 0 ms 0 KB -