oj.uz

Submission #535220

# Submission time Handle Problem Language Result Execution time Memory
535220 2022-03-09T17:29:03 Z NaimSS 007 (CEOI14_007) C++14
30 / 100
 242 ms 25536 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);
    }
    assert(sz(S[a])==1 && sz(S[b])==1);
    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;
      swap(a,b);
      if(d1[a]+m <= d2[a] && d1[b] + m < d2[b])bom=1;
      swap(a,b);
      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:98:5: note: in expansion of macro 'dbg'
   98 |     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:111:7: note: in expansion of macro 'dbg'
  111 |       dbg(m,bom);
      |       ^~~

Subtask #1
9.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14412 KB Output is correct
2 Partially correct 10 ms 14368 KB Partially correct
3 Partially correct 10 ms 14380 KB Partially correct
4 Correct 7 ms 14412 KB Output is correct
5 Correct 11 ms 14392 KB Output is correct
6 Partially correct 9 ms 14328 KB Partially correct
7 Partially correct 8 ms 14412 KB Partially correct
8 Correct 8 ms 14412 KB Output is correct
9 Partially correct 8 ms 14412 KB Partially correct
10 Correct 8 ms 14412 KB Output is correct
11 Correct 8 ms 14372 KB Output is correct
12 Correct 8 ms 14412 KB Output is correct
13 Partially correct 9 ms 14412 KB Partially correct
14 Correct 7 ms 14432 KB Output is correct
15 Partially correct 10 ms 14412 KB Partially correct
16 Correct 8 ms 14412 KB Output is correct
17 Correct 8 ms 14412 KB Output is correct
18 Correct 8 ms 14444 KB Output is correct
19 Partially correct 8 ms 14412 KB Partially correct
20 Partially correct 9 ms 14420 KB Partially correct
21 Correct 8 ms 14412 KB Output is correct
22 Partially correct 8 ms 14332 KB Partially correct
23 Partially correct 9 ms 14412 KB Partially correct
24 Correct 8 ms 14412 KB Output is correct

Subtask #2
21.0 / 70.0

# Verdict Execution time Memory Grader output
1 Partially correct 28 ms 15948 KB Partially correct
2 Correct 33 ms 16716 KB Output is correct
3 Partially correct 58 ms 16084 KB Partially correct
4 Correct 44 ms 16708 KB Output is correct
5 Correct 36 ms 15932 KB Output is correct
6 Correct 31 ms 16116 KB Output is correct
7 Partially correct 31 ms 16264 KB Partially correct
8 Partially correct 31 ms 16284 KB Partially correct
9 Correct 57 ms 16836 KB Output is correct
10 Partially correct 125 ms 21008 KB Partially correct
11 Correct 52 ms 17904 KB Output is correct
12 Partially correct 73 ms 18932 KB Partially correct
13 Correct 70 ms 18224 KB Output is correct
14 Correct 74 ms 17572 KB Output is correct
15 Partially correct 80 ms 19012 KB Partially correct
16 Correct 69 ms 19200 KB Output is correct
17 Partially correct 60 ms 18628 KB Partially correct
18 Correct 92 ms 18628 KB Output is correct
19 Partially correct 97 ms 19840 KB Partially correct
20 Correct 153 ms 22600 KB Output is correct
21 Correct 84 ms 20676 KB Output is correct
22 Partially correct 108 ms 19892 KB Partially correct
23 Partially correct 107 ms 20604 KB Partially correct
24 Partially correct 89 ms 20560 KB Partially correct
25 Correct 89 ms 20168 KB Output is correct
26 Partially correct 91 ms 19916 KB Partially correct
27 Partially correct 122 ms 20676 KB Partially correct
28 Partially correct 134 ms 20656 KB Partially correct
29 Partially correct 121 ms 21316 KB Partially correct
30 Correct 189 ms 23492 KB Output is correct
31 Correct 106 ms 21640 KB Output is correct
32 Partially correct 125 ms 20676 KB Partially correct
33 Partially correct 108 ms 20764 KB Partially correct
34 Correct 118 ms 21124 KB Output is correct
35 Correct 88 ms 20880 KB Output is correct
36 Correct 118 ms 21120 KB Output is correct
37 Correct 133 ms 22004 KB Output is correct
38 Partially correct 117 ms 21756 KB Partially correct
39 Partially correct 132 ms 21956 KB Partially correct
40 Correct 169 ms 23360 KB Output is correct
41 Partially correct 242 ms 25536 KB Partially correct