oj.uz

Submission #961023

# Submission time Handle Problem Language Result Execution time Memory
961023 2024-04-11T12:06:53 Z noyancanturk Senior Postmen (BOI14_postmen) C++17
55 / 100
 310 ms 19220 KB 
#ifndef Local
    #pragma GCC optimize("O3,unroll-loops")
#endif
    
#include "bits/stdc++.h"
using namespace std;
    
#define int int64_t
#define pb push_back
    
const int lim=2e5+100;
const int mod=998244353;
//const int mod=(1ll<<61)-1;
 
using pii=pair<int,int>;

vector<pii>v[lim];
bool vis[lim];
vector<int>path;

void dfs(int node){
    while(v[node].size()){
        pii now=v[node].back();
        v[node].pop_back();
        if(vis[now.second])continue;
        vis[now.second]=1;
        dfs(now.first);
    }
    path.pb(node);
}

inline void solve(){
    int n,m;
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int x,y;
        cin>>x>>y;
        v[x].pb({y,i});
        v[y].pb({x,i});
    }
    dfs(1);
    vector<int>cur;
    bool seen[n+1];
    memset(seen,0,sizeof(seen));
    for(int j:path){
        cerr<<j<<" ";
        if(seen[j]){
            cout<<j<<" ";
            while(cur.back()!=j){
                cout<<cur.back()<<" ";
                seen[cur.back()]=0;
                cur.pop_back();
            } 
            cout<<"\n";
        }else{
            cur.push_back(j);
            seen[j]=1;
        }
    }
}
    
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
#ifdef Local  
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
#endif
    int t=1;
    //cin>>t;
    while (t--)
    {
        solve();
    }
}

Subtask #1
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 2 ms 5112 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 10 ms 5468 KB Output is correct
5 Correct 5 ms 5212 KB Output is correct
6 Correct 13 ms 5560 KB Output is correct
7 Correct 38 ms 7248 KB Output is correct
8 Correct 7 ms 5468 KB Output is correct
9 Correct 244 ms 16156 KB Output is correct
10 Correct 10 ms 5464 KB Output is correct
11 Correct 13 ms 5444 KB Output is correct
12 Correct 253 ms 17040 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 10 ms 5468 KB Output is correct
5 Correct 5 ms 5208 KB Output is correct
6 Correct 13 ms 5724 KB Output is correct
7 Correct 38 ms 7256 KB Output is correct
8 Correct 7 ms 5468 KB Output is correct
9 Correct 241 ms 16160 KB Output is correct
10 Correct 10 ms 5468 KB Output is correct
11 Correct 9 ms 5468 KB Output is correct
12 Correct 251 ms 16940 KB Output is correct
13 Correct 256 ms 19052 KB Output is correct
14 Correct 290 ms 16272 KB Output is correct
15 Correct 288 ms 18120 KB Output is correct
16 Correct 258 ms 19196 KB Output is correct
17 Correct 301 ms 13668 KB Output is correct
18 Correct 310 ms 17080 KB Output is correct

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 10 ms 5468 KB Output is correct
5 Correct 4 ms 5464 KB Output is correct
6 Correct 17 ms 5784 KB Output is correct
7 Correct 39 ms 7236 KB Output is correct
8 Correct 7 ms 5464 KB Output is correct
9 Correct 246 ms 16308 KB Output is correct
10 Correct 10 ms 5464 KB Output is correct
11 Correct 9 ms 5720 KB Output is correct
12 Correct 288 ms 16960 KB Output is correct
13 Correct 268 ms 19116 KB Output is correct
14 Correct 293 ms 16440 KB Output is correct
15 Correct 294 ms 18028 KB Output is correct
16 Correct 287 ms 19220 KB Output is correct
17 Correct 290 ms 13536 KB Output is correct
18 Correct 286 ms 16832 KB Output is correct
19 Runtime error 5 ms 10076 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -