oj.uz

Submission #535232

# Submission time Handle Problem Language Result Execution time Memory
535232 2022-03-09T17:54:04 Z NaimSS 007 (CEOI14_007) C++14
0 / 100
 276 ms 19604 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 n,m;

vi g[N];

vi dista(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;
}

int s,d,a,b;
vi d1,d2;
int vis[N][2];
int dist[N][2];
int vamo(int m){
  queue<pii> q;
  q.push(pii(d,1));
  int inicio=0;
  while(!q.empty()){
    auto it = q.front();
    q.pop();
    int v = it.ff;
    int turn = it.ss;
    if(dist[v][turn] == m && !inicio){
      inicio = 1;
      q.push(pii(s,0));
      if(vis[s][1] && dist[s][1] == m){
        vis[s][1] = 2;
      }else if(!vis[s][1]){
        vis[s][1] = 2;
      }
    }
    if(vis[it.ff][it.ss])continue;
    vis[v][turn] = 1;
    
    for(auto to : g[v]){
      if(vis[to][turn])continue;
      if(vis[to][turn^1]){
        if(turn == 1)continue;
        if(turn == 0 && dist[v][0] + 1 <= dist[to][turn^1]){
          vis[to][turn^1]=2;
        }
      }else {
        if(turn == 0)vis[to][1]=2;
      }
      if(dist[to][turn] == 0 && !vis[to][turn]){
        dist[to][turn] = dist[v][turn] + 1;
        q.push(pii(to,turn));
      }
    }
  }
  return (vis[a][1] == 1 || vis[b][1] == 1) ? 0 : 1;
}

int32_t main(){
    fastio;
    cin >> n >> m;
    cin >> s >> d >> a >> b;
    assert(a!=b);
    while(m--){
      int u,v;
      cin >> u >> v;
      g[u].pb(v);
      g[v].pb(u);
    }
     d1 = dista(s),d2=dista(d);

    int l = 0,r = n,ans = -1;
        while(l<=r){
      int m =(l+r)/2;
      int bom=0;
      if(d1[a]+m < d2[a] && d1[b] + m < d2[b])bom=1;
      dbg(m,bom);
      if(bom){
        ans = m;
        l = m+1;
      }else r=m-1;
    }
    if(vamo(ans+1))ans++;
    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:139:7: note: in expansion of macro 'dbg'
  139 |       dbg(m,bom);
      |       ^~~

Subtask #1
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 5016 KB Output is correct
4 Incorrect 4 ms 4940 KB Output isn't correct
5 Incorrect 3 ms 4940 KB Output isn't correct
6 Correct 3 ms 4940 KB Output is correct
7 Correct 3 ms 4940 KB Output is correct
8 Incorrect 3 ms 5008 KB Output isn't correct
9 Correct 3 ms 4940 KB Output is correct
10 Correct 3 ms 5024 KB Output is correct
11 Correct 3 ms 4940 KB Output is correct
12 Incorrect 3 ms 5024 KB Output isn't correct
13 Correct 3 ms 5068 KB Output is correct
14 Incorrect 3 ms 4940 KB Output isn't correct
15 Correct 3 ms 4940 KB Output is correct
16 Incorrect 3 ms 5068 KB Output isn't correct
17 Incorrect 3 ms 5024 KB Output isn't correct
18 Incorrect 3 ms 5068 KB Output isn't correct
19 Correct 3 ms 5188 KB Output is correct
20 Correct 3 ms 5028 KB Output is correct
21 Correct 4 ms 5032 KB Output is correct
22 Correct 3 ms 5068 KB Output is correct
23 Correct 3 ms 5068 KB Output is correct
24 Incorrect 3 ms 5068 KB Output isn't correct

Subtask #2
0.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 7712 KB Output is correct
2 Incorrect 32 ms 8852 KB Output isn't correct
3 Correct 28 ms 7892 KB Output is correct
4 Incorrect 31 ms 8928 KB Output isn't correct
5 Correct 30 ms 7572 KB Output is correct
6 Correct 28 ms 7872 KB Output is correct
7 Correct 44 ms 8228 KB Output is correct
8 Correct 31 ms 8260 KB Output is correct
9 Incorrect 42 ms 8680 KB Output isn't correct
10 Correct 125 ms 13244 KB Output is correct
11 Incorrect 76 ms 10544 KB Output isn't correct
12 Correct 98 ms 11832 KB Output is correct
13 Incorrect 65 ms 11008 KB Output isn't correct
14 Correct 57 ms 10088 KB Output is correct
15 Correct 80 ms 11940 KB Output is correct
16 Correct 96 ms 12272 KB Output is correct
17 Correct 84 ms 11592 KB Output is correct
18 Incorrect 91 ms 11532 KB Output isn't correct
19 Correct 113 ms 12904 KB Output is correct
20 Incorrect 184 ms 15740 KB Output isn't correct
21 Incorrect 105 ms 14380 KB Output isn't correct
22 Correct 110 ms 13212 KB Output is correct
23 Correct 148 ms 14316 KB Output is correct
24 Correct 97 ms 14168 KB Output is correct
25 Incorrect 119 ms 13808 KB Output isn't correct
26 Correct 111 ms 13288 KB Output is correct
27 Correct 125 ms 14372 KB Output is correct
28 Correct 132 ms 14456 KB Output is correct
29 Correct 168 ms 14700 KB Output is correct
30 Incorrect 216 ms 16580 KB Output isn't correct
31 Incorrect 123 ms 15684 KB Output isn't correct
32 Correct 134 ms 14348 KB Output is correct
33 Correct 128 ms 14608 KB Output is correct
34 Incorrect 145 ms 15032 KB Output isn't correct
35 Incorrect 109 ms 14680 KB Output isn't correct
36 Incorrect 99 ms 14948 KB Output isn't correct
37 Correct 171 ms 16200 KB Output is correct
38 Correct 156 ms 16124 KB Output is correct
39 Correct 174 ms 16064 KB Output is correct
40 Incorrect 191 ms 17496 KB Output isn't correct
41 Correct 276 ms 19604 KB Output is correct