oj.uz

Submission #961026

# Submission time Handle Problem Language Result Execution time Memory
961026 2024-04-11T12:08:56 Z noyancanturk Senior Postmen (BOI14_postmen) C++17
55 / 100
 500 ms 81080 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=5e5+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 5 ms 12380 KB Output is correct
2 Correct 4 ms 12380 KB Output is correct
3 Correct 4 ms 12380 KB Output is correct
4 Correct 12 ms 12892 KB Output is correct
5 Correct 7 ms 12632 KB Output is correct
6 Correct 16 ms 12892 KB Output is correct
7 Correct 42 ms 14424 KB Output is correct
8 Correct 9 ms 12780 KB Output is correct
9 Correct 272 ms 22944 KB Output is correct
10 Correct 12 ms 12636 KB Output is correct
11 Correct 11 ms 12636 KB Output is correct
12 Correct 267 ms 23500 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12380 KB Output is correct
2 Correct 4 ms 12380 KB Output is correct
3 Correct 4 ms 12380 KB Output is correct
4 Correct 14 ms 12892 KB Output is correct
5 Correct 7 ms 12636 KB Output is correct
6 Correct 15 ms 12892 KB Output is correct
7 Correct 45 ms 14684 KB Output is correct
8 Correct 9 ms 12636 KB Output is correct
9 Correct 244 ms 22736 KB Output is correct
10 Correct 14 ms 12632 KB Output is correct
11 Correct 11 ms 12636 KB Output is correct
12 Correct 250 ms 23444 KB Output is correct
13 Correct 269 ms 25284 KB Output is correct
14 Correct 289 ms 22384 KB Output is correct
15 Correct 284 ms 24508 KB Output is correct
16 Correct 275 ms 25408 KB Output is correct
17 Correct 290 ms 19872 KB Output is correct
18 Correct 307 ms 23060 KB Output is correct

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12380 KB Output is correct
2 Correct 5 ms 12380 KB Output is correct
3 Correct 4 ms 12380 KB Output is correct
4 Correct 18 ms 12636 KB Output is correct
5 Correct 7 ms 12668 KB Output is correct
6 Correct 15 ms 12892 KB Output is correct
7 Correct 46 ms 14468 KB Output is correct
8 Correct 9 ms 12632 KB Output is correct
9 Correct 258 ms 22940 KB Output is correct
10 Correct 13 ms 12636 KB Output is correct
11 Correct 12 ms 12636 KB Output is correct
12 Correct 248 ms 23500 KB Output is correct
13 Correct 257 ms 25360 KB Output is correct
14 Correct 281 ms 22468 KB Output is correct
15 Correct 299 ms 24504 KB Output is correct
16 Correct 287 ms 25384 KB Output is correct
17 Correct 298 ms 19832 KB Output is correct
18 Correct 290 ms 23088 KB Output is correct
19 Execution timed out 1063 ms 81080 KB Time limit exceeded
20 Halted 0 ms 0 KB -