oj.uz

Submission #488015

# Submission time Handle Problem Language Result Execution time Memory
488015 2021-11-17T12:19:08 Z urosk Senior Postmen (BOI14_postmen) C++14
55 / 100
 500 ms 98232 KB 
// __builtin_popcount(x) broj bitova
// __builtin_popcountll(x)
// __builtin_clz(x) vodece nule
// __builtin_clzll(x)
// __builtin_ctz(x) nule na pocetku
// __builtin_ctzll(x)
// 2000000011
// 2000000033
#include "bits/stdc++.h"
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define ld double
#define ll int
#define ull unsigned long long
#define llinf 100000000000000000LL // 10^17
#define iinf 2000000000 // 2*10^9
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define sz(a) int(a.size())
#define all(a) a.begin(),a.end()
#define rall(a) a.begin(),a.end(),greater<int>()
#define getunique(v) {sort(all(v)); v.erase(unique(all(v)), v.end());}
#define pi 3.14159265358979323846
#define here cerr<<"---------------------------\n"
#define ceri(a,l,r) {for(ll i = l;i<=r;i++) cerr<<a[i]<< " ";cerr<<endl;}
#define ceri2(a,l,r,n,m) {for(ll i = l;i<=r;i++){for(ll j = n;j<=m;j++) cerr<<a[i][j]<< " ";cerr<<endl;}}
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
using namespace std;
using namespace __gnu_pbds;

typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll rnd(ll l,ll r){
    return uniform_int_distribution<ll>(l,r)(rng);
}

void setIO(string inoutname)
{
	freopen((inoutname+".in").c_str(),"r",stdin);
    	freopen((inoutname+".out").c_str(),"w",stdout);
}
#define mod 1
ll gcd(ll a, ll b)
{
   if(b==0) return a;
   if(a==0) return b;
   if(a>=b)  return gcd(a%b,b);
   return  gcd(a,b%a);
}
ll lcm(ll a,ll b){
   return (a/gcd(a,b))*b;
}
ll add(ll a,ll b){
	a+=b;
	if(a<0) a+=mod;
	if(a>=mod) a%=mod;
	return a;
}
ll mul(ll a,ll b){return(a*b)%mod;}
#define maxn 500005
set<ll> g[maxn];
ll n,m;
bool vis[maxn];
vector<ll> ans;
void euler(ll u){
    while(sz(g[u])){
        ll s = *g[u].begin();
        g[u].erase(g[u].find(s));
        g[s].erase(g[s].find(u));
        euler(s);
    }
    ans.pb(u);
    vis[u] = 1;
}
void tc(){
	ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);
    cin >> n >> m;
    for(ll i = 1;i<=m;i++){
        ll x,y; cin >> x >> y;
        g[x].insert(y);
        g[y].insert(x);
    }
    for(ll i = 1;i<=n;i++) if(!vis[i]) euler(i);
    fill(vis,vis+n+1,0);
    vector<ll> v;
    //ceri(ans,0,sz(ans)-1);
    for(ll x : ans){
        if(vis[x]==1){
            vector<ll> w;
            while(v.back()!=x){
                w.pb(v.back());
                v.popb();
            }
            w.pb(x);
            for(ll y : w){
                vis[y] = 0;
                cout<<y<< " ";
            }
            cout<<endl;
            vis[x] = 1;
        }else vis[x] = 1,v.pb(x);
    }
}
int main(){
	ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);
	//setIO("lol");
	int t; t = 1;
	while(t--){
		tc();
	}
	return 0;
}

Compilation message

postmen.cpp: In function 'void setIO(std::string)':
postmen.cpp:47:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |  freopen((inoutname+".in").c_str(),"r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
postmen.cpp:48:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |      freopen((inoutname+".out").c_str(),"w",stdout);
      |      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23756 KB Output is correct
2 Correct 11 ms 23688 KB Output is correct
3 Correct 11 ms 23804 KB Output is correct
4 Correct 13 ms 24140 KB Output is correct
5 Correct 15 ms 23840 KB Output is correct
6 Correct 15 ms 24396 KB Output is correct
7 Correct 23 ms 25944 KB Output is correct
8 Correct 12 ms 24072 KB Output is correct
9 Correct 114 ms 38108 KB Output is correct
10 Correct 13 ms 24140 KB Output is correct
11 Correct 13 ms 24012 KB Output is correct
12 Correct 137 ms 38420 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23756 KB Output is correct
2 Correct 11 ms 23756 KB Output is correct
3 Correct 11 ms 23804 KB Output is correct
4 Correct 14 ms 24156 KB Output is correct
5 Correct 12 ms 23856 KB Output is correct
6 Correct 14 ms 24332 KB Output is correct
7 Correct 28 ms 25948 KB Output is correct
8 Correct 13 ms 24012 KB Output is correct
9 Correct 132 ms 38112 KB Output is correct
10 Correct 13 ms 24164 KB Output is correct
11 Correct 13 ms 24012 KB Output is correct
12 Correct 112 ms 38260 KB Output is correct
13 Correct 98 ms 38504 KB Output is correct
14 Correct 90 ms 38520 KB Output is correct
15 Correct 102 ms 38428 KB Output is correct
16 Correct 100 ms 38516 KB Output is correct
17 Correct 99 ms 38448 KB Output is correct
18 Correct 107 ms 35560 KB Output is correct

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23788 KB Output is correct
2 Correct 12 ms 23756 KB Output is correct
3 Correct 12 ms 23756 KB Output is correct
4 Correct 13 ms 24140 KB Output is correct
5 Correct 12 ms 23884 KB Output is correct
6 Correct 14 ms 24416 KB Output is correct
7 Correct 22 ms 25916 KB Output is correct
8 Correct 13 ms 24012 KB Output is correct
9 Correct 137 ms 38116 KB Output is correct
10 Correct 13 ms 24140 KB Output is correct
11 Correct 12 ms 24064 KB Output is correct
12 Correct 119 ms 38300 KB Output is correct
13 Correct 90 ms 38440 KB Output is correct
14 Correct 101 ms 38468 KB Output is correct
15 Correct 104 ms 38392 KB Output is correct
16 Correct 85 ms 38472 KB Output is correct
17 Correct 99 ms 38424 KB Output is correct
18 Correct 112 ms 35444 KB Output is correct
19 Correct 457 ms 98232 KB Output is correct
20 Execution timed out 591 ms 98056 KB Time limit exceeded
21 Halted 0 ms 0 KB -