oj.uz

Submission #535218

# Submission time Handle Problem Language Result Execution time Memory
535218 2022-03-09T17:27:05 Z NaimSS 007 (CEOI14_007) C++14
30 / 100
 225 ms 25684 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
9.0 / 30.0

# Verdict Execution time Memory Grader output
1 Partially correct 8 ms 14412 KB Partially correct
2 Partially correct 8 ms 14412 KB Partially correct
3 Partially correct 9 ms 14412 KB Partially correct
4 Correct 7 ms 14412 KB Output is correct
5 Correct 7 ms 14412 KB Output is correct
6 Partially correct 7 ms 14412 KB Partially correct
7 Partially correct 8 ms 14340 KB Partially correct
8 Correct 8 ms 14332 KB Output is correct
9 Partially correct 8 ms 14412 KB Partially correct
10 Partially correct 8 ms 14368 KB Partially correct
11 Partially correct 8 ms 14412 KB Partially correct
12 Correct 9 ms 14412 KB Output is correct
13 Partially correct 8 ms 14412 KB Partially correct
14 Correct 7 ms 14412 KB Output is correct
15 Partially correct 8 ms 14412 KB Partially correct
16 Correct 9 ms 14356 KB Output is correct
17 Correct 8 ms 14444 KB Output is correct
18 Correct 7 ms 14412 KB Output is correct
19 Partially correct 7 ms 14412 KB Partially correct
20 Partially correct 9 ms 14404 KB Partially correct
21 Partially correct 7 ms 14412 KB Partially correct
22 Partially correct 8 ms 14412 KB Partially correct
23 Partially correct 8 ms 14372 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 34 ms 15948 KB Partially correct
2 Correct 33 ms 16652 KB Output is correct
3 Partially correct 31 ms 16076 KB Partially correct
4 Correct 35 ms 16792 KB Output is correct
5 Partially correct 27 ms 15964 KB Partially correct
6 Partially correct 27 ms 16116 KB Partially correct
7 Partially correct 30 ms 16332 KB Partially correct
8 Partially correct 35 ms 16328 KB Partially correct
9 Correct 51 ms 16664 KB Output is correct
10 Partially correct 155 ms 21088 KB Partially correct
11 Correct 54 ms 17936 KB Output is correct
12 Partially correct 73 ms 18880 KB Partially correct
13 Correct 76 ms 18268 KB Output is correct
14 Correct 53 ms 17600 KB Output is correct
15 Partially correct 78 ms 18908 KB Partially correct
16 Partially correct 75 ms 19240 KB Partially correct
17 Partially correct 62 ms 18660 KB Partially correct
18 Correct 65 ms 18676 KB Output is correct
19 Partially correct 98 ms 19840 KB Partially correct
20 Correct 152 ms 22676 KB Output is correct
21 Correct 86 ms 20696 KB Output is correct
22 Partially correct 91 ms 19860 KB Partially correct
23 Partially correct 90 ms 20612 KB Partially correct
24 Partially correct 107 ms 20508 KB Partially correct
25 Correct 102 ms 20176 KB Output is correct
26 Partially correct 80 ms 19836 KB Partially correct
27 Partially correct 100 ms 20588 KB Partially correct
28 Partially correct 121 ms 20676 KB Partially correct
29 Partially correct 122 ms 21208 KB Partially correct
30 Correct 171 ms 23328 KB Output is correct
31 Correct 117 ms 21560 KB Output is correct
32 Partially correct 109 ms 20616 KB Partially correct
33 Partially correct 96 ms 20844 KB Partially correct
34 Correct 113 ms 21176 KB Output is correct
35 Correct 87 ms 20804 KB Output is correct
36 Correct 94 ms 21072 KB Output is correct
37 Partially correct 122 ms 21916 KB Partially correct
38 Partially correct 116 ms 21832 KB Partially correct
39 Partially correct 132 ms 21916 KB Partially correct
40 Correct 185 ms 23428 KB Output is correct
41 Partially correct 225 ms 25684 KB Partially correct