oj.uz

답안 #881107

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
881107 2023-11-30T15:23:26 Z Requiem 어르신 집배원 (BOI14_postmen) C++17
100 / 100
 428 ms 82360 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,v,m,deg[MAXN],complexity=0;
bool used[MAXN];
bool solve[MAXN];
ii edge[MAXN];
vector<int> ans;
void dfs(int u){
    while(!g[u].empty()){
        int id = g[u].back();
        g[u].pop_back();
        if (used[id]) continue;
        used[id] = true;
        int v = edge[id].fi + edge[id].se - u;
        dfs(v);
    }
    ans.pb(u);
}
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));
    dfs(1);
    if (ans.size() != m + 1) {
        cout<<"IMPOSSIBLE"<<endl;
        return 0;
    }
    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:40:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   40 | main()
      | ^~~~
postmen.cpp: In function 'int main()':
postmen.cpp:49:13: warning: unused variable 'u' [-Wunused-variable]
   49 |         int u,v;
      |             ^
postmen.cpp:49:15: warning: unused variable 'v' [-Wunused-variable]
   49 |         int u,v;
      |               ^
postmen.cpp:71:20: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   71 |     if (ans.size() != m + 1) {
      |         ~~~~~~~~~~~^~~~~~~~
postmen.cpp:44:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |         freopen(TASKNAME".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
postmen.cpp:45:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |         freopen(TASKNAME".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
38.0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 16988 KB Output is correct
2 Correct 4 ms 16988 KB Output is correct
3 Correct 4 ms 16988 KB Output is correct
4 Correct 4 ms 17244 KB Output is correct
5 Correct 4 ms 17244 KB Output is correct
6 Correct 4 ms 17500 KB Output is correct
7 Correct 9 ms 18780 KB Output is correct
8 Correct 4 ms 17244 KB Output is correct
9 Correct 27 ms 25056 KB Output is correct
10 Correct 4 ms 17244 KB Output is correct
11 Correct 4 ms 17244 KB Output is correct
12 Correct 31 ms 25304 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 17200 KB Output is correct
2 Correct 3 ms 16988 KB Output is correct
3 Correct 3 ms 16988 KB Output is correct
4 Correct 4 ms 17492 KB Output is correct
5 Correct 3 ms 17240 KB Output is correct
6 Correct 4 ms 17500 KB Output is correct
7 Correct 7 ms 18524 KB Output is correct
8 Correct 4 ms 17244 KB Output is correct
9 Correct 26 ms 25056 KB Output is correct
10 Correct 4 ms 17240 KB Output is correct
11 Correct 4 ms 17240 KB Output is correct
12 Correct 29 ms 25308 KB Output is correct
13 Correct 40 ms 27340 KB Output is correct
14 Correct 39 ms 24004 KB Output is correct
15 Correct 39 ms 26712 KB Output is correct
16 Correct 44 ms 28272 KB Output is correct
17 Correct 41 ms 22744 KB Output is correct
18 Correct 40 ms 26308 KB Output is correct

Subtask #3
45.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 16988 KB Output is correct
2 Correct 3 ms 16988 KB Output is correct
3 Correct 4 ms 16984 KB Output is correct
4 Correct 4 ms 17240 KB Output is correct
5 Correct 3 ms 17244 KB Output is correct
6 Correct 4 ms 17500 KB Output is correct
7 Correct 7 ms 18524 KB Output is correct
8 Correct 4 ms 17240 KB Output is correct
9 Correct 30 ms 25096 KB Output is correct
10 Correct 5 ms 17240 KB Output is correct
11 Correct 5 ms 17244 KB Output is correct
12 Correct 28 ms 25304 KB Output is correct
13 Correct 41 ms 27076 KB Output is correct
14 Correct 41 ms 24016 KB Output is correct
15 Correct 36 ms 26956 KB Output is correct
16 Correct 41 ms 28152 KB Output is correct
17 Correct 48 ms 22912 KB Output is correct
18 Correct 40 ms 26312 KB Output is correct
19 Correct 417 ms 82356 KB Output is correct
20 Correct 350 ms 67596 KB Output is correct
21 Correct 324 ms 75848 KB Output is correct
22 Correct 378 ms 82360 KB Output is correct
23 Correct 127 ms 65212 KB Output is correct
24 Correct 411 ms 55044 KB Output is correct
25 Correct 428 ms 72008 KB Output is correct