oj.uz

Submission #598878

# Submission time Handle Problem Language Result Execution time Memory
598878 2022-07-19T06:55:38 Z balbit Fountain Parks (IOI21_parks) C++17
5 / 100
 453 ms 55600 KB 
// 我的心裡只有你沒有他

#include "parks.h"
#include <bits/stdc++.h>
// #define int ll
using namespace std;
#define ll long long
#define y1 zck_is_king
#define pii pair<ll, ll>
#define ull unsigned ll
#define f first
#define s second
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define SQ(x) (x)*(x)
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define REP(i,n) for (int i = 0; i<n; ++i)
#define RREP(i,n) for (int i = n-1; i>=0; --i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#ifdef BALBIT
#define IOS()
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define bug(...)
#endif

const int maxn = 4e5+5;
vector<int> rU,rV,rA,rB;
set<pii> used; // benches in use
map<pii, int> id; 

void ADD(int u, int v, int a, int b) {
    rU.pb(u);
    rV.pb(v);
    rA.pb(a);
    rB.pb(b);
    used.insert({a,b});
}


int GET(int x, int y){
    return id.count({x,y})?id[{x,y}]:-1;
}

int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};
bool seen[maxn];

vector<int> X, Y; 

void dfs(int v, int sd) { //sd: starting direction
    seen[v]= 1;
    int x = X[v], y = Y[v];
    for (int df = 0; df < 4; ++df) {
        int d = (df + sd) % 4;
        int tx = x + dx[d]*2, ty = y + dy[d]*2;
        int u = GET(tx,ty);
        if (u == -1 || seen[u]) continue;

        int pd = (d-1+4)%4;
        int nxtd = (d+1)%4;

        int b1x = x + dx[d] + dx[pd], b1y = y + dy[d] + dy[pd];
        int b2x = x + dx[d] + dx[nxtd], b2y = y + dy[d] + dy[nxtd];

        bug(v,u,d);
        bug(b1x,b1y);
        bug(b2x,b2y);

        if (!used.count({b1x, b1y})) {
            ADD(u,v,b1x,b1y);
        }else{
            continue;
            assert(!used.count({b2x,b2y}));
            ADD(u,v,b2x,b2y);
        }
        dfs(u, pd);
    }
}


int construct_roads(std::vector<int> _x, std::vector<int> _y) {
    X = _x, Y = _y;
    int n = SZ(X);
    REP(i,n) {
        id[{X[i], Y[i]}] = i;
    }

    dfs(0, 0);

    if (SZ(rU) < n-1) return 0;
    build(rU,rV,rA,rB);
    return 1;
}

/*
4, 4, 6, 4, 2], [4, 6, 4, 2, 4

5
4 4
4 6
6 4
4 2
2 4

25
-4 4
0 0
0 2
0 4
0 6
0 8
-2 0
-2 2
-2 4
-2 6
-2 8
-4 0
-4 2

-4 6
-4 8
-6 0
-6 2
-6 4
-6 6
-6 8
-8 0
-8 2
-8 4
-8 6
-8 8
*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 183 ms 27212 KB Output is correct
10 Correct 13 ms 3156 KB Output is correct
11 Correct 86 ms 15152 KB Output is correct
12 Correct 20 ms 4704 KB Output is correct
13 Correct 45 ms 8864 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 163 ms 24008 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 183 ms 27212 KB Output is correct
10 Correct 13 ms 3156 KB Output is correct
11 Correct 86 ms 15152 KB Output is correct
12 Correct 20 ms 4704 KB Output is correct
13 Correct 45 ms 8864 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 163 ms 24008 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 429 ms 55600 KB Output is correct
24 Incorrect 0 ms 212 KB Solution announced impossible, but it is possible.
25 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 183 ms 27212 KB Output is correct
10 Correct 13 ms 3156 KB Output is correct
11 Correct 86 ms 15152 KB Output is correct
12 Correct 20 ms 4704 KB Output is correct
13 Correct 45 ms 8864 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 163 ms 24008 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 429 ms 55600 KB Output is correct
24 Incorrect 0 ms 212 KB Solution announced impossible, but it is possible.
25 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 183 ms 27212 KB Output is correct
10 Correct 13 ms 3156 KB Output is correct
11 Correct 86 ms 15152 KB Output is correct
12 Correct 20 ms 4704 KB Output is correct
13 Correct 45 ms 8864 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 163 ms 24008 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Incorrect 175 ms 17488 KB Solution announced impossible, but it is possible.
21 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 183 ms 27212 KB Output is correct
10 Correct 13 ms 3156 KB Output is correct
11 Correct 86 ms 15152 KB Output is correct
12 Correct 20 ms 4704 KB Output is correct
13 Correct 45 ms 8864 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 163 ms 24008 KB Output is correct
17 Correct 453 ms 54648 KB Output is correct
18 Correct 436 ms 49316 KB Output is correct
19 Incorrect 151 ms 17772 KB Solution announced impossible, but it is possible.
20 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 183 ms 27212 KB Output is correct
10 Correct 13 ms 3156 KB Output is correct
11 Correct 86 ms 15152 KB Output is correct
12 Correct 20 ms 4704 KB Output is correct
13 Correct 45 ms 8864 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 163 ms 24008 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 429 ms 55600 KB Output is correct
24 Incorrect 0 ms 212 KB Solution announced impossible, but it is possible.
25 Halted 0 ms 0 KB -