Submission #727476

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
727476	2023-04-20T20:50:17 Z	n0sk1ll	007 (CEOI14_007)	C++17	0 / 100	235 ms	23692 KB

#include <bits/stdc++.h>

#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0)
#define mp make_pair
#define xx first
#define yy second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define all(x) x.begin(),x.end()
#define ff(i,a,b) for (int i = a; i < b; i++)
#define fff(i,a,b) for (int i = a; i <= b; i++)
#define bff(i,a,b) for (int i = b-1; i >= a; i--)
#define bfff(i,a,b) for (int i = b; i >= a; i--)

using namespace std;
long double typedef ld;
unsigned int typedef ui;
long long int typedef li;
pair<int,int> typedef pii;
pair<li,li> typedef pli;
pair<ld,ld> typedef pld;
vector<vector<int>> typedef graph;
unsigned long long int typedef ull;
//const int mod = 998244353;
const int mod = 1000000007;







//Note to self: Check for overflow

graph g(200005);
bool vis[200005];
int duba[200005];
int dubb[200005];

bool moze(int n, int ona, int on, int wait)
{
    fff(i,1,n) vis[i]=false;

    //cout<<"cekam koliko: "<<wait<<endl;

    //cout<<"razlica: ";

    queue<pii> bfs;
    bfs.push({on,wait});
    while (!bfs.empty())
    {
        auto [p,d]=bfs.front(); bfs.pop();
        if (vis[p]) continue; vis[p]=true; //cout<<p<<" ";
        if (duba[p]<duba[ona]) return false;
        if (dubb[p]<dubb[ona]) return false;
        if (d==0) continue;
        for (auto it : g[p]) bfs.push({it,d-1});
    }
    return true;
}

int main()
{
    FAST;

    int n,m; cin>>n>>m;
    int ona,on,a,b; cin>>ona>>on>>a>>b;
    while (m--)
    {
        int u,v; cin>>u>>v;
        g[u].pb(v),g[v].pb(u);
    }

    queue<pii> bfs;

    bfs.push({a,0});
    while (!bfs.empty())
    {
        auto [p,d]=bfs.front(); bfs.pop();
        if (vis[p]) continue; vis[p]=1,duba[p]=d;
        for (auto it : g[p]) bfs.push({it,d+1});
    }

    fff(i,1,n) vis[i]=false;
    bfs.push({b,0});
    while (!bfs.empty())
    {
        auto [p,d]=bfs.front(); bfs.pop();
        if (vis[p]) continue; vis[p]=1,dubb[p]=d;
        for (auto it : g[p]) bfs.push({it,d+1});
    }

    int l=-1,r=min(duba[on],dubb[on]);
    while (r-l>1)
    {
        int mid=(l+r)/2;
        if (moze(n,ona,on,mid)) l=mid;
        else r=mid;

        //cout<<endl<<endl;
    }

    cout<<l<<"\n";
}

//Note to self: Check for overflow

Compilation message

007.cpp: In function 'bool moze(int, int, int, int)':
007.cpp:55:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   55 |         if (vis[p]) continue; vis[p]=true; //cout<<p<<" ";
      |         ^~
007.cpp:55:31: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   55 |         if (vis[p]) continue; vis[p]=true; //cout<<p<<" ";
      |                               ^~~
007.cpp: In function 'int main()':
007.cpp:82:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   82 |         if (vis[p]) continue; vis[p]=1,duba[p]=d;
      |         ^~
007.cpp:82:31: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   82 |         if (vis[p]) continue; vis[p]=1,duba[p]=d;
      |                               ^~~
007.cpp:91:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   91 |         if (vis[p]) continue; vis[p]=1,dubb[p]=d;
      |         ^~
007.cpp:91:31: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   91 |         if (vis[p]) continue; vis[p]=1,dubb[p]=d;
      |                               ^~~

Subtask #1
0.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	4948 KB	Output is correct
2	Correct	3 ms	4948 KB	Output is correct
3	Correct	3 ms	4996 KB	Output is correct
4	Incorrect	3 ms	4948 KB	Output isn't correct
5	Incorrect	3 ms	5044 KB	Output isn't correct
6	Correct	3 ms	5044 KB	Output is correct
7	Correct	3 ms	5040 KB	Output is correct
8	Incorrect	3 ms	4948 KB	Output isn't correct
9	Correct	3 ms	4948 KB	Output is correct
10	Correct	3 ms	4948 KB	Output is correct
11	Correct	3 ms	4948 KB	Output is correct
12	Incorrect	3 ms	4948 KB	Output isn't correct
13	Correct	3 ms	5076 KB	Output is correct
14	Incorrect	3 ms	5040 KB	Output isn't correct
15	Correct	3 ms	5044 KB	Output is correct
16	Incorrect	3 ms	5076 KB	Output isn't correct
17	Incorrect	3 ms	5076 KB	Output isn't correct
18	Incorrect	3 ms	5076 KB	Output isn't correct
19	Correct	3 ms	5076 KB	Output is correct
20	Correct	3 ms	5076 KB	Output is correct
21	Correct	3 ms	5076 KB	Output is correct
22	Correct	3 ms	5076 KB	Output is correct
23	Correct	5 ms	5076 KB	Output is correct
24	Incorrect	3 ms	5076 KB	Output isn't correct

Subtask #2
0.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	7124 KB	Output is correct
2	Incorrect	23 ms	8064 KB	Output isn't correct
3	Correct	17 ms	7252 KB	Output is correct
4	Incorrect	23 ms	8140 KB	Output isn't correct
5	Correct	17 ms	7068 KB	Output is correct
6	Correct	17 ms	7356 KB	Output is correct
7	Correct	19 ms	7496 KB	Output is correct
8	Correct	20 ms	7520 KB	Output is correct
9	Incorrect	36 ms	8336 KB	Output isn't correct
10	Correct	137 ms	17124 KB	Output is correct
11	Incorrect	46 ms	9716 KB	Output isn't correct
12	Correct	67 ms	11004 KB	Output is correct
13	Incorrect	47 ms	10028 KB	Output isn't correct
14	Correct	37 ms	9380 KB	Output is correct
15	Correct	54 ms	11060 KB	Output is correct
16	Correct	56 ms	11316 KB	Output is correct
17	Correct	58 ms	10684 KB	Output is correct
18	Incorrect	49 ms	10656 KB	Output isn't correct
19	Correct	82 ms	13024 KB	Output is correct
20	Incorrect	169 ms	19020 KB	Output isn't correct
21	Incorrect	74 ms	13388 KB	Output isn't correct
22	Correct	63 ms	12232 KB	Output is correct
23	Correct	98 ms	13216 KB	Output is correct
24	Correct	77 ms	13256 KB	Output is correct
25	Incorrect	62 ms	12808 KB	Output isn't correct
26	Correct	98 ms	12348 KB	Output is correct
27	Correct	75 ms	13356 KB	Output is correct
28	Correct	79 ms	13472 KB	Output is correct
29	Correct	114 ms	15436 KB	Output is correct
30	Incorrect	185 ms	19900 KB	Output isn't correct
31	Incorrect	81 ms	14632 KB	Output isn't correct
32	Correct	71 ms	13448 KB	Output is correct
33	Correct	81 ms	13552 KB	Output is correct
34	Incorrect	81 ms	14156 KB	Output isn't correct
35	Incorrect	71 ms	13732 KB	Output isn't correct
36	Incorrect	71 ms	14032 KB	Output isn't correct
37	Correct	154 ms	15176 KB	Output is correct
38	Correct	96 ms	14948 KB	Output is correct
39	Correct	92 ms	15032 KB	Output is correct
40	Incorrect	171 ms	18688 KB	Output isn't correct
41	Correct	235 ms	23692 KB	Output is correct

Submission #727476

Compilation message

Subtask #1 0.0 / 30.0

Subtask #2 0.0 / 70.0

Subtask #1
0.0 / 30.0

Subtask #2
0.0 / 70.0