답안 #960732

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
960732	2024-04-11T01:59:02 Z	GrindMachine	007 (CEOI14_007)	C++17	100 / 100	217 ms	36040 KB

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a,b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a,b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif

/*

read the edi some time ago, remember some ideas from there

*/

const int MOD = 1e9 + 7;
const int N = 2e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

vector<int> adj1[N], adj2[N];
vector<bool> vis(N);
vector<int> topo;

void dfs1(int u){
    vis[u] = 1;
    trav(v,adj2[u]){
        if(vis[v]) conts;
        dfs1(v);
    }

    topo.pb(u);
}

void solve(int test_case)
{
    int n,m; cin >> n >> m;
    int s,d,x,y; cin >> s >> d >> x >> y;
    rep1(i,m){
        int u,v; cin >> u >> v;
        adj1[u].pb(v), adj1[v].pb(u);
    }

    auto bfs = [&](int src){
        queue<int> q;
        vector<int> dis(n+5,inf1);
        q.push(src);
        dis[src] = 0;

        while(!q.empty()){
            int u = q.front();
            q.pop();

            trav(v,adj1[u]){
                if(dis[v] != inf1) conts;
                q.push(v);
                dis[v] = dis[u]+1;
            }
        }

        return dis;
    };

    auto disd = bfs(d);
    auto disx = bfs(x);
    auto disy = bfs(y);

    rep1(u,n){
        trav(v,adj1[u]){
            if(disx[v] == disx[u]-1 and disy[v] == disy[u]-1){
                adj2[u].pb(v);
            }
        }
    }

    rep1(i,n){
        if(vis[i]) conts;
        dfs1(i);
    }

    vector<int> dp(n+5);
    trav(u,topo){
        trav(v,adj2[u]){
            amax(dp[u],dp[v]+1);
        }
    }

    vector<bool> win(n+5); // does 007 win if dr.null starts at u (no turns skipped)?
    rep1(u,n){
        int x1 = disx[s], y1 = disy[s];
        int x2 = disx[u], y2 = disy[u];
        bool curr_win;

        if(x2 < x1 or y2 < y1){
            curr_win = false;
        }
        else{
            if(x1 < x2 or y1 < y2){
                curr_win = true;
            }
            else{
                if(dp[u] > dp[s]){
                    curr_win = false;
                }
                else{
                    curr_win = true;
                }
            }
        }

        win[u] = curr_win;
    }

    vector<bool> dis_win(n+5,1);
    rep1(u,n){
        if(!win[u]){
            // cant wait for time = dis(u,d)
            dis_win[disd[u]] = 0;
        }
    }

    int ans = -1;
    rep(i,n+1){
        if(!dis_win[i]) break;
        ans = i;
    }

    cout << ans << endl;
}

int main()
{
    fastio;

    int t = 1;
    // cin >> t;

    rep1(i, t) {
        solve(i);
    }

    return 0;
}

Subtask #1
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	9816 KB	Output is correct
2	Correct	3 ms	9820 KB	Output is correct
3	Correct	3 ms	9820 KB	Output is correct
4	Correct	2 ms	9652 KB	Output is correct
5	Correct	2 ms	9820 KB	Output is correct
6	Correct	2 ms	9820 KB	Output is correct
7	Correct	2 ms	9820 KB	Output is correct
8	Correct	2 ms	9820 KB	Output is correct
9	Correct	3 ms	9820 KB	Output is correct
10	Correct	2 ms	9820 KB	Output is correct
11	Correct	3 ms	9820 KB	Output is correct
12	Correct	3 ms	9820 KB	Output is correct
13	Correct	3 ms	9820 KB	Output is correct
14	Correct	3 ms	9820 KB	Output is correct
15	Correct	3 ms	9820 KB	Output is correct
16	Correct	3 ms	9820 KB	Output is correct
17	Correct	3 ms	9820 KB	Output is correct
18	Correct	3 ms	9820 KB	Output is correct
19	Correct	3 ms	9820 KB	Output is correct
20	Correct	4 ms	9820 KB	Output is correct
21	Correct	3 ms	9820 KB	Output is correct
22	Correct	3 ms	9816 KB	Output is correct
23	Correct	3 ms	9820 KB	Output is correct
24	Correct	4 ms	9884 KB	Output is correct

Subtask #2
70.0 / 70.0

#	결과	실행 시간	메모리	Grader output
1	Correct	18 ms	13784 KB	Output is correct
2	Correct	24 ms	15592 KB	Output is correct
3	Correct	19 ms	14040 KB	Output is correct
4	Correct	25 ms	15860 KB	Output is correct
5	Correct	19 ms	13524 KB	Output is correct
6	Correct	22 ms	14296 KB	Output is correct
7	Correct	21 ms	14544 KB	Output is correct
8	Correct	21 ms	14544 KB	Output is correct
9	Correct	38 ms	15320 KB	Output is correct
10	Correct	107 ms	25804 KB	Output is correct
11	Correct	39 ms	18548 KB	Output is correct
12	Correct	53 ms	20700 KB	Output is correct
13	Correct	43 ms	19064 KB	Output is correct
14	Correct	40 ms	17716 KB	Output is correct
15	Correct	64 ms	20800 KB	Output is correct
16	Correct	70 ms	21392 KB	Output is correct
17	Correct	44 ms	20144 KB	Output is correct
18	Correct	48 ms	20192 KB	Output is correct
19	Correct	87 ms	22176 KB	Output is correct
20	Correct	147 ms	29128 KB	Output is correct
21	Correct	76 ms	25464 KB	Output is correct
22	Correct	60 ms	22988 KB	Output is correct
23	Correct	79 ms	25420 KB	Output is correct
24	Correct	72 ms	25204 KB	Output is correct
25	Correct	90 ms	24012 KB	Output is correct
26	Correct	81 ms	23264 KB	Output is correct
27	Correct	74 ms	25036 KB	Output is correct
28	Correct	106 ms	25032 KB	Output is correct
29	Correct	141 ms	25632 KB	Output is correct
30	Correct	151 ms	30564 KB	Output is correct
31	Correct	93 ms	27940 KB	Output is correct
32	Correct	75 ms	24788 KB	Output is correct
33	Correct	99 ms	25808 KB	Output is correct
34	Correct	108 ms	26336 KB	Output is correct
35	Correct	120 ms	26052 KB	Output is correct
36	Correct	93 ms	26812 KB	Output is correct
37	Correct	120 ms	28592 KB	Output is correct
38	Correct	102 ms	27848 KB	Output is correct
39	Correct	118 ms	27852 KB	Output is correct
40	Correct	193 ms	30308 KB	Output is correct
41	Correct	217 ms	36040 KB	Output is correct

답안 #960732

Compilation message

Subtask #1 30.0 / 30.0

Subtask #2 70.0 / 70.0

Subtask #1
30.0 / 30.0

Subtask #2
70.0 / 70.0