oj.uz

Submission #535234

# Submission time Handle Problem Language Result Execution time Memory
535234 2022-03-09T17:58:58 Z NaimSS 007 (CEOI14_007) C++14
0 / 100
 308 ms 19140 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){
  ms(dist,-1);
  queue<pii> q;
  dist[d][1] = 0;
  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;
      dist[s][0] = m;
      q.push(pii(s,0));
    }
    if(turn == 1 && dist[v][turn^1] == dist[v][turn])continue;
    if(vis[it.ff][it.ss])continue;
    vis[v][turn] = 1;
    
    for(auto to : g[v]){
      if(vis[to][turn])continue;
      if(dist[to][turn] == -1 && !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:130:7: note: in expansion of macro 'dbg'
  130 |       dbg(m,bom);
      |       ^~~

Subtask #1
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Partially correct 3 ms 6476 KB Partially correct
2 Correct 4 ms 6592 KB Output is correct
3 Correct 4 ms 6476 KB Output is correct
4 Incorrect 3 ms 6476 KB Output isn't correct
5 Incorrect 3 ms 6476 KB Output isn't correct
6 Correct 4 ms 6476 KB Output is correct
7 Correct 3 ms 6476 KB Output is correct
8 Incorrect 4 ms 6476 KB Output isn't correct
9 Correct 3 ms 6476 KB Output is correct
10 Partially correct 4 ms 6476 KB Partially correct
11 Partially correct 3 ms 6476 KB Partially correct
12 Incorrect 5 ms 6604 KB Output isn't correct
13 Correct 4 ms 6604 KB Output is correct
14 Incorrect 5 ms 6476 KB Output isn't correct
15 Partially correct 4 ms 6604 KB Partially correct
16 Incorrect 4 ms 6604 KB Output isn't correct
17 Incorrect 4 ms 6604 KB Output isn't correct
18 Incorrect 3 ms 6604 KB Output isn't correct
19 Correct 4 ms 6604 KB Output is correct
20 Correct 5 ms 6608 KB Output is correct
21 Partially correct 3 ms 6604 KB Partially correct
22 Partially correct 4 ms 6604 KB Partially correct
23 Partially correct 4 ms 6604 KB Partially correct
24 Incorrect 4 ms 6604 KB Output isn't correct

Subtask #2
0.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 8444 KB Output is correct
2 Incorrect 39 ms 9296 KB Output isn't correct
3 Correct 28 ms 8524 KB Output is correct
4 Incorrect 33 ms 9420 KB Output isn't correct
5 Partially correct 28 ms 8380 KB Partially correct
6 Partially correct 28 ms 8624 KB Partially correct
7 Partially correct 31 ms 8828 KB Partially correct
8 Partially correct 44 ms 8900 KB Partially correct
9 Incorrect 46 ms 9284 KB Output isn't correct
10 Correct 125 ms 13716 KB Output is correct
11 Incorrect 86 ms 10752 KB Output isn't correct
12 Correct 92 ms 11940 KB Output is correct
13 Incorrect 89 ms 11168 KB Output isn't correct
14 Correct 64 ms 10396 KB Output is correct
15 Correct 86 ms 11972 KB Output is correct
16 Partially correct 92 ms 12240 KB Partially correct
17 Partially correct 82 ms 11620 KB Partially correct
18 Correct 86 ms 11716 KB Output is correct
19 Correct 98 ms 12868 KB Output is correct
20 Incorrect 172 ms 15764 KB Output isn't correct
21 Incorrect 165 ms 14148 KB Output isn't correct
22 Correct 110 ms 12996 KB Output is correct
23 Correct 111 ms 14016 KB Output is correct
24 Correct 106 ms 13900 KB Output is correct
25 Incorrect 156 ms 13504 KB Output isn't correct
26 Correct 100 ms 13192 KB Output is correct
27 Partially correct 123 ms 14116 KB Partially correct
28 Partially correct 183 ms 14144 KB Partially correct
29 Correct 142 ms 14608 KB Output is correct
30 Incorrect 201 ms 16488 KB Output isn't correct
31 Incorrect 171 ms 15224 KB Output isn't correct
32 Correct 199 ms 13960 KB Output is correct
33 Correct 132 ms 14312 KB Output is correct
34 Incorrect 150 ms 14588 KB Output isn't correct
35 Incorrect 124 ms 14308 KB Output isn't correct
36 Incorrect 118 ms 14552 KB Output isn't correct
37 Partially correct 165 ms 15724 KB Partially correct
38 Partially correct 172 ms 15516 KB Partially correct
39 Partially correct 205 ms 15464 KB Partially correct
40 Incorrect 221 ms 17020 KB Output isn't correct
41 Correct 308 ms 19140 KB Output is correct