oj.uz

Submission #535219

# Submission time Handle Problem Language Result Execution time Memory
535219 2022-03-09T17:28:09 Z NaimSS 007 (CEOI14_007) C++14
30 / 100
 229 ms 25616 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);
    }
    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[b] + m < d2[b])bom=1;
      swap(a,b);
      if(d1[a]+m <= d2[a] && d1[b] + 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:97:5: note: in expansion of macro 'dbg'
   97 |     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:110:7: note: in expansion of macro 'dbg'
  110 |       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 Partially correct 7 ms 14412 KB Partially correct
3 Partially correct 9 ms 14352 KB Partially correct
4 Correct 7 ms 14412 KB Output is correct
5 Correct 7 ms 14412 KB Output is correct
6 Partially correct 7 ms 14320 KB Partially correct
7 Partially correct 8 ms 14412 KB Partially correct
8 Correct 8 ms 14328 KB Output is correct
9 Partially correct 9 ms 14412 KB Partially correct
10 Correct 7 ms 14412 KB Output is correct
11 Correct 8 ms 14424 KB Output is correct
12 Correct 10 ms 14412 KB Output is correct
13 Partially correct 7 ms 14368 KB Partially correct
14 Correct 7 ms 14412 KB Output is correct
15 Partially correct 7 ms 14368 KB Partially correct
16 Correct 10 ms 14412 KB Output is correct
17 Correct 8 ms 14412 KB Output is correct
18 Correct 8 ms 14412 KB Output is correct
19 Partially correct 10 ms 14456 KB Partially correct
20 Partially correct 8 ms 14540 KB Partially correct
21 Correct 8 ms 14444 KB Output is correct
22 Partially correct 8 ms 14412 KB Partially correct
23 Partially correct 8 ms 14412 KB Partially correct
24 Correct 9 ms 14348 KB Output is correct

Subtask #2
21.0 / 70.0

# Verdict Execution time Memory Grader output
1 Partially correct 38 ms 15980 KB Partially correct
2 Correct 36 ms 16648 KB Output is correct
3 Partially correct 29 ms 16068 KB Partially correct
4 Correct 34 ms 16804 KB Output is correct
5 Correct 27 ms 15948 KB Output is correct
6 Correct 26 ms 16096 KB Output is correct
7 Partially correct 31 ms 16284 KB Partially correct
8 Partially correct 31 ms 16252 KB Partially correct
9 Correct 53 ms 16824 KB Output is correct
10 Partially correct 116 ms 21192 KB Partially correct
11 Correct 51 ms 17860 KB Output is correct
12 Partially correct 71 ms 18884 KB Partially correct
13 Correct 72 ms 18252 KB Output is correct
14 Correct 51 ms 17564 KB Output is correct
15 Partially correct 70 ms 18860 KB Partially correct
16 Correct 67 ms 19140 KB Output is correct
17 Partially correct 62 ms 18680 KB Partially correct
18 Correct 72 ms 18628 KB Output is correct
19 Partially correct 102 ms 19864 KB Partially correct
20 Correct 162 ms 22620 KB Output is correct
21 Correct 90 ms 20696 KB Output is correct
22 Partially correct 88 ms 19884 KB Partially correct
23 Partially correct 112 ms 20516 KB Partially correct
24 Partially correct 102 ms 20548 KB Partially correct
25 Correct 86 ms 20164 KB Output is correct
26 Partially correct 93 ms 19820 KB Partially correct
27 Partially correct 107 ms 20608 KB Partially correct
28 Partially correct 109 ms 20632 KB Partially correct
29 Partially correct 122 ms 21320 KB Partially correct
30 Correct 172 ms 23396 KB Output is correct
31 Correct 114 ms 21540 KB Output is correct
32 Partially correct 134 ms 20568 KB Partially correct
33 Partially correct 108 ms 20792 KB Partially correct
34 Correct 113 ms 21108 KB Output is correct
35 Correct 102 ms 20824 KB Output is correct
36 Correct 87 ms 21096 KB Output is correct
37 Correct 122 ms 22004 KB Output is correct
38 Partially correct 133 ms 22048 KB Partially correct
39 Partially correct 134 ms 21876 KB Partially correct
40 Correct 182 ms 23436 KB Output is correct
41 Partially correct 229 ms 25616 KB Partially correct