oj.uz

Submission #535217

# Submission time Handle Problem Language Result Execution time Memory
535217 2022-03-09T17:26:24 Z NaimSS 007 (CEOI14_007) C++14
0 / 100
 246 ms 25540 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;
      
      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:108:7: note: in expansion of macro 'dbg'
  108 |       dbg(m,bom);
      |       ^~~

Subtask #1
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 7 ms 14412 KB Output is correct
3 Correct 7 ms 14412 KB Output is correct
4 Incorrect 8 ms 14412 KB Output isn't correct
5 Incorrect 8 ms 14424 KB Output isn't correct
6 Correct 9 ms 14412 KB Output is correct
7 Correct 8 ms 14412 KB Output is correct
8 Incorrect 10 ms 14412 KB Output isn't correct
9 Correct 9 ms 14412 KB Output is correct
10 Correct 8 ms 14412 KB Output is correct
11 Correct 10 ms 14412 KB Output is correct
12 Incorrect 8 ms 14412 KB Output isn't correct
13 Correct 7 ms 14412 KB Output is correct
14 Incorrect 9 ms 14412 KB Output isn't correct
15 Correct 9 ms 14412 KB Output is correct
16 Incorrect 8 ms 14412 KB Output isn't correct
17 Incorrect 8 ms 14412 KB Output isn't correct
18 Incorrect 7 ms 14412 KB Output isn't correct
19 Correct 8 ms 14448 KB Output is correct
20 Correct 7 ms 14412 KB Output is correct
21 Correct 9 ms 14408 KB Output is correct
22 Correct 8 ms 14452 KB Output is correct
23 Correct 8 ms 14412 KB Output is correct
24 Incorrect 8 ms 14412 KB Output isn't correct

Subtask #2
0.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 15976 KB Output is correct
2 Incorrect 34 ms 16664 KB Output isn't correct
3 Correct 29 ms 16080 KB Output is correct
4 Incorrect 33 ms 16844 KB Output isn't correct
5 Correct 31 ms 15952 KB Output is correct
6 Correct 29 ms 16136 KB Output is correct
7 Correct 33 ms 16324 KB Output is correct
8 Correct 42 ms 16368 KB Output is correct
9 Incorrect 43 ms 16696 KB Output isn't correct
10 Correct 118 ms 21112 KB Output is correct
11 Incorrect 51 ms 17932 KB Output isn't correct
12 Correct 88 ms 18968 KB Output is correct
13 Incorrect 77 ms 18244 KB Output isn't correct
14 Correct 56 ms 17600 KB Output is correct
15 Correct 76 ms 18900 KB Output is correct
16 Correct 69 ms 19176 KB Output is correct
17 Correct 65 ms 18696 KB Output is correct
18 Incorrect 92 ms 18628 KB Output isn't correct
19 Correct 100 ms 19784 KB Output is correct
20 Incorrect 163 ms 22724 KB Output isn't correct
21 Incorrect 87 ms 20612 KB Output isn't correct
22 Correct 81 ms 19812 KB Output is correct
23 Correct 89 ms 20580 KB Output is correct
24 Correct 90 ms 20560 KB Output is correct
25 Incorrect 90 ms 20160 KB Output isn't correct
26 Correct 84 ms 19940 KB Output is correct
27 Correct 94 ms 20676 KB Output is correct
28 Correct 119 ms 20644 KB Output is correct
29 Correct 119 ms 21216 KB Output is correct
30 Incorrect 162 ms 23364 KB Output isn't correct
31 Incorrect 105 ms 21632 KB Output isn't correct
32 Correct 101 ms 20640 KB Output is correct
33 Correct 100 ms 20864 KB Output is correct
34 Incorrect 123 ms 21140 KB Output isn't correct
35 Incorrect 100 ms 20860 KB Output isn't correct
36 Incorrect 89 ms 21128 KB Output isn't correct
37 Correct 119 ms 22040 KB Output is correct
38 Correct 122 ms 21828 KB Output is correct
39 Correct 134 ms 21828 KB Output is correct
40 Incorrect 185 ms 23444 KB Output isn't correct
41 Correct 246 ms 25540 KB Output is correct