oj.uz

Submission #535222

# Submission time Handle Problem Language Result Execution time Memory
535222 2022-03-09T17:32:40 Z NaimSS 007 (CEOI14_007) C++14
30 / 100
 239 ms 25520 KB 
#include <bits/stdc++.h>
#define ld long double
#define endl "\n"
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb push_back
#define mp(a,b) make_pair(a,b)
#define ms(v,x) memset(v,x,sizeof(v))
#define all(v) v.begin(),v.end()
#define ff first
#define ss second
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define per(i, a, b) for(int i = b-1; i>=a ; i--)
#define trav(a, x) for(auto& a : x)
#define allin(a , x) for(auto a : x)
#define Unique(v) sort(all(v));v.erase(unique(all(v)),v.end());
#define sz(v) ((int)v.size())
using namespace std;
typedef vector<int> vi;
#define y1 abacaba
//#define left oooooopss
#define db(x) cerr << #x <<" == "<<x << endl;
#define db2(x,y) cerr<<#x <<" == "<<x<<", "<<#y<<" == "<<y<<endl;
#define db3(x,y,z) cerr << #x<<" == "<<x<<", "<<#y<<" == "<<y<<", "<<#z<<" == "<<z<<endl;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<ll> vl;
std::mt19937 rng((int) std::chrono::steady_clock::now().time_since_epoch().count());
ll cdiv(ll a, ll b) { return a/b+((a^b)>0&&a%b); } // divide a by b rounded up
ll fdiv(ll a, ll b) { return a/b-((a^b)<0&&a%b); } // divide a by b rounded down
inline ll mod(ll n, ll m ){ ll ret = n%m; if(ret < 0) ret += m; return ret; }
ll gcd(ll a, ll b){return (b == 0LL ? a : gcd(b, a%b));}
ll exp(ll b,ll e,ll m){
  b%=m;
  ll ans = 1;
  for (; e; b = b * b % m, e /= 2)
      if (e & 1) ans = ans * b % m;
  return ans;
}

// debug:
void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T){ 
  cerr << ' ' << H; 
  dbg_out(T...); 
}
#ifdef LOCAL
#define dbg(...) cerr<<"(" << #__VA_ARGS__<<"):" , dbg_out(__VA_ARGS__) , cerr << endl
#else
#define dbg(...) 42
#endif
//

const int N = 200100;
int d[N];
int vis[N];
    int n,m;

vi g[N];

vi dist(int a){
  vector<int> d(n+2);
  rep(i,1,n+1)d[i] = 1e9;
  d[a] = 0;
  priority_queue<pii,vector<pii>,greater<pii>> pq;
  pq.push(pii(d[a],a));
  while(!pq.empty()){
    auto t = pq.top();pq.pop();
    if(t.ff != d[t.ss])continue;
    int v = t.ss;
    for(auto to : g[v])if(d[to] > d[v] + 1){
      d[to] = d[v] + 1;
      pq.push(pii(d[to],to));
    }
  }
  return d;
}
set<int> S[N];

int32_t main(){
    fastio;
    cin >> n >> m;
    int s,d,a,b;
    cin >> s >> d >> a >> b;
    assert(a!=b);
    while(m--){
      int u,v;
      cin >> u >> v;
      if(v==a || v==b)S[u].insert(v);
      if(u==a || u==b)S[v].insert(u);
      g[u].pb(v);
      g[v].pb(u);
    }
    assert(sz(S[a])==1 && sz(S[b])==1);
    vi d1 = dist(s),d2=dist(d);

    int l = 0,r = n,ans = -1;
    dbg(d1[a],d2[a],d1[b],d2[b]);
    vi good;
    rep(i,1,n+1)if(sz(S[i]) == 2)good.pb(i);
    while(l<=r){
      int m =(l+r)/2;
      int bom=0;
      if(d1[a]+m <= d2[a] && d1[a] + 1 + m <= d2[b])bom=1;
      swap(a,b);
      if(d1[a]+m <= d2[a] && d1[a] + 1 + m <= d2[b])bom=1;
      swap(a,b);
      for(auto to : good){
        if(d1[to] + m < d2[a] && d1[to] + m < d2[b])bom = 1;
      }
      dbg(m,bom);
      if(bom){
        ans = m;
        l = m+1;
      }else r=m-1;
    }
    cout << ans << endl;

    // math -> gcd it all
    // Did u check N=1? Did you switch N,M?
}

Compilation message

007.cpp: In function 'int32_t main()':
007.cpp:50:18: warning: statement has no effect [-Wunused-value]
   50 | #define dbg(...) 42
      |                  ^~
007.cpp:98:5: note: in expansion of macro 'dbg'
   98 |     dbg(d1[a],d2[a],d1[b],d2[b]);
      |     ^~~
007.cpp:50:18: warning: statement has no effect [-Wunused-value]
   50 | #define dbg(...) 42
      |                  ^~
007.cpp:111:7: note: in expansion of macro 'dbg'
  111 |       dbg(m,bom);
      |       ^~~

Subtask #1
9.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14412 KB Output is correct
2 Correct 8 ms 14412 KB Output is correct
3 Partially correct 8 ms 14424 KB Partially correct
4 Correct 7 ms 14412 KB Output is correct
5 Correct 8 ms 14412 KB Output is correct
6 Partially correct 8 ms 14412 KB Partially correct
7 Partially correct 8 ms 14412 KB Partially correct
8 Correct 7 ms 14412 KB Output is correct
9 Partially correct 8 ms 14412 KB Partially correct
10 Correct 8 ms 14412 KB Output is correct
11 Correct 7 ms 14412 KB Output is correct
12 Correct 10 ms 14376 KB Output is correct
13 Partially correct 8 ms 14412 KB Partially correct
14 Correct 8 ms 14412 KB Output is correct
15 Partially correct 8 ms 14464 KB Partially correct
16 Correct 8 ms 14328 KB Output is correct
17 Correct 9 ms 14416 KB Output is correct
18 Correct 9 ms 14412 KB Output is correct
19 Partially correct 7 ms 14412 KB Partially correct
20 Partially correct 7 ms 14456 KB Partially correct
21 Correct 7 ms 14412 KB Output is correct
22 Partially correct 8 ms 14392 KB Partially correct
23 Partially correct 8 ms 14448 KB Partially correct
24 Correct 8 ms 14468 KB Output is correct

Subtask #2
21.0 / 70.0

# Verdict Execution time Memory Grader output
1 Partially correct 29 ms 16028 KB Partially correct
2 Correct 33 ms 16756 KB Output is correct
3 Partially correct 29 ms 16076 KB Partially correct
4 Correct 31 ms 16816 KB Output is correct
5 Correct 31 ms 16064 KB Output is correct
6 Correct 27 ms 16080 KB Output is correct
7 Partially correct 31 ms 16328 KB Partially correct
8 Partially correct 35 ms 16248 KB Partially correct
9 Correct 54 ms 16720 KB Output is correct
10 Partially correct 127 ms 21072 KB Partially correct
11 Correct 53 ms 17880 KB Output is correct
12 Partially correct 76 ms 18856 KB Partially correct
13 Correct 65 ms 18268 KB Output is correct
14 Correct 50 ms 17652 KB Output is correct
15 Partially correct 73 ms 18900 KB Partially correct
16 Correct 80 ms 19100 KB Output is correct
17 Partially correct 59 ms 18632 KB Partially correct
18 Correct 65 ms 18628 KB Output is correct
19 Partially correct 91 ms 19856 KB Partially correct
20 Correct 166 ms 22688 KB Output is correct
21 Correct 88 ms 20692 KB Output is correct
22 Partially correct 84 ms 19816 KB Partially correct
23 Correct 85 ms 20548 KB Output is correct
24 Partially correct 82 ms 20512 KB Partially correct
25 Correct 91 ms 20292 KB Output is correct
26 Correct 111 ms 19820 KB Output is correct
27 Partially correct 113 ms 20652 KB Partially correct
28 Partially correct 125 ms 20724 KB Partially correct
29 Partially correct 119 ms 21204 KB Partially correct
30 Correct 185 ms 23268 KB Output is correct
31 Correct 105 ms 21700 KB Output is correct
32 Partially correct 103 ms 20552 KB Partially correct
33 Correct 109 ms 20744 KB Output is correct
34 Correct 139 ms 21240 KB Output is correct
35 Correct 90 ms 20776 KB Output is correct
36 Correct 89 ms 21072 KB Output is correct
37 Correct 134 ms 21956 KB Output is correct
38 Partially correct 140 ms 21760 KB Partially correct
39 Partially correct 140 ms 21908 KB Partially correct
40 Correct 172 ms 23468 KB Output is correct
41 Partially correct 239 ms 25520 KB Partially correct