oj.uz

Submission #535216

# Submission time Handle Problem Language Result Execution time Memory
535216 2022-03-09T17:19:56 Z NaimSS 007 (CEOI14_007) C++14
0 / 100
 219 ms 16144 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;
}

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;
      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]);
    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;
    }
    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:94:5: note: in expansion of macro 'dbg'
   94 |     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:99:7: note: in expansion of macro 'dbg'
   99 |       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 2 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Incorrect 3 ms 4940 KB Output isn't correct
5 Incorrect 2 ms 4940 KB Output isn't correct
6 Correct 3 ms 4952 KB Output is correct
7 Correct 3 ms 4940 KB Output is correct
8 Incorrect 3 ms 4940 KB Output isn't correct
9 Correct 3 ms 4940 KB Output is correct
10 Correct 3 ms 4940 KB Output is correct
11 Correct 3 ms 5008 KB Output is correct
12 Incorrect 3 ms 4940 KB Output isn't correct
13 Correct 3 ms 4940 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 4940 KB Output isn't correct
17 Incorrect 3 ms 4940 KB Output isn't correct
18 Incorrect 3 ms 4940 KB Output isn't correct
19 Correct 3 ms 4940 KB Output is correct
20 Correct 3 ms 4940 KB Output is correct
21 Correct 3 ms 4940 KB Output is correct
22 Correct 3 ms 4940 KB Output is correct
23 Correct 3 ms 4940 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 21 ms 6576 KB Output is correct
2 Incorrect 26 ms 7372 KB Output isn't correct
3 Correct 24 ms 6712 KB Output is correct
4 Incorrect 26 ms 7372 KB Output isn't correct
5 Correct 23 ms 6476 KB Output is correct
6 Correct 20 ms 6764 KB Output is correct
7 Correct 24 ms 6876 KB Output is correct
8 Correct 26 ms 6916 KB Output is correct
9 Incorrect 34 ms 7296 KB Output isn't correct
10 Correct 118 ms 11624 KB Output is correct
11 Incorrect 47 ms 8516 KB Output isn't correct
12 Correct 68 ms 9420 KB Output is correct
13 Incorrect 59 ms 8900 KB Output isn't correct
14 Correct 40 ms 8132 KB Output is correct
15 Correct 58 ms 9476 KB Output is correct
16 Correct 63 ms 9740 KB Output is correct
17 Correct 56 ms 9272 KB Output is correct
18 Incorrect 61 ms 9284 KB Output isn't correct
19 Correct 90 ms 10484 KB Output is correct
20 Incorrect 158 ms 13212 KB Output isn't correct
21 Incorrect 77 ms 11220 KB Output isn't correct
22 Correct 84 ms 10416 KB Output is correct
23 Correct 78 ms 11168 KB Output is correct
24 Correct 81 ms 11052 KB Output is correct
25 Incorrect 89 ms 10824 KB Output isn't correct
26 Correct 76 ms 10468 KB Output is correct
27 Correct 87 ms 11224 KB Output is correct
28 Correct 97 ms 11308 KB Output is correct
29 Correct 114 ms 11860 KB Output is correct
30 Incorrect 176 ms 13868 KB Output isn't correct
31 Incorrect 148 ms 12156 KB Output isn't correct
32 Correct 113 ms 11236 KB Output is correct
33 Correct 91 ms 11400 KB Output is correct
34 Incorrect 105 ms 11724 KB Output isn't correct
35 Incorrect 90 ms 11460 KB Output isn't correct
36 Incorrect 79 ms 11728 KB Output isn't correct
37 Correct 123 ms 12644 KB Output is correct
38 Correct 112 ms 12340 KB Output is correct
39 Correct 119 ms 12516 KB Output is correct
40 Incorrect 159 ms 14020 KB Output isn't correct
41 Correct 219 ms 16144 KB Output is correct