oj.uz

Submission #535215

# Submission time Handle Problem Language Result Execution time Memory
535215 2022-03-09T17:19:24 Z NaimSS 007 (CEOI14_007) C++14
30 / 100
 217 ms 23456 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
9.0 / 30.0

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

Subtask #2
21.0 / 70.0

# Verdict Execution time Memory Grader output
1 Partially correct 21 ms 7120 KB Partially correct
2 Correct 26 ms 8004 KB Output is correct
3 Partially correct 24 ms 7164 KB Partially correct
4 Correct 27 ms 8100 KB Output is correct
5 Partially correct 23 ms 6988 KB Partially correct
6 Partially correct 20 ms 7244 KB Partially correct
7 Partially correct 25 ms 7456 KB Partially correct
8 Partially correct 34 ms 7496 KB Partially correct
9 Correct 35 ms 8296 KB Output is correct
10 Partially correct 117 ms 16868 KB Partially correct
11 Correct 47 ms 9540 KB Output is correct
12 Partially correct 67 ms 10948 KB Partially correct
13 Correct 57 ms 10072 KB Output is correct
14 Correct 42 ms 9220 KB Output is correct
15 Partially correct 61 ms 10864 KB Partially correct
16 Partially correct 65 ms 11248 KB Partially correct
17 Partially correct 60 ms 10564 KB Partially correct
18 Correct 64 ms 10600 KB Output is correct
19 Partially correct 88 ms 12996 KB Partially correct
20 Correct 151 ms 18836 KB Output is correct
21 Correct 82 ms 13380 KB Output is correct
22 Partially correct 80 ms 12172 KB Partially correct
23 Partially correct 81 ms 13116 KB Partially correct
24 Partially correct 83 ms 13016 KB Partially correct
25 Correct 88 ms 12804 KB Output is correct
26 Partially correct 78 ms 12252 KB Partially correct
27 Partially correct 91 ms 13216 KB Partially correct
28 Partially correct 97 ms 13252 KB Partially correct
29 Partially correct 119 ms 15132 KB Partially correct
30 Correct 171 ms 19780 KB Output is correct
31 Correct 98 ms 14472 KB Output is correct
32 Partially correct 98 ms 13208 KB Partially correct
33 Partially correct 93 ms 13520 KB Partially correct
34 Correct 112 ms 13908 KB Output is correct
35 Correct 91 ms 13612 KB Output is correct
36 Correct 89 ms 14020 KB Output is correct
37 Partially correct 115 ms 15108 KB Partially correct
38 Partially correct 114 ms 14788 KB Partially correct
39 Partially correct 121 ms 14888 KB Partially correct
40 Correct 154 ms 18580 KB Output is correct
41 Partially correct 217 ms 23456 KB Partially correct