oj.uz

답안 #438837

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
438837 2021-06-28T17:27:37 Z teehandsome 분수 공원 (IOI21_parks) C++17
15 / 100
 206 ms 29252 KB 
#include "parks.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define endl '\n'
#define INF (int) 1e9+7
#define all(x) x.begin(),x.end()
using namespace std;
using namespace __gnu_pbds;
using ll=long long;
using pii=pair<int,int>;
using ppi=pair<int,pii>;

template<typename T>
using oset=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

template<typename AA,typename BB>
void _print(vector<pair<AA,BB>> x) {cerr<<"["; int cnt_temp12=0;
    for(auto e:x) {
            if(cnt_temp12) cerr<<", ";
            cerr<<"{"<<e.first<<","<<e.second<<"}"; ++cnt_temp12;} cerr<<"]";
    }
template<typename AA,typename BB>
void _print(pair<AA,BB> x) {cerr<<"{"<<x.first<<","<<x.second<<"}";}
template<typename T>
void _print(vector<T> x) {cerr<<"{"; int cnt_temp12=0;
    for(auto e:x) {
            if(cnt_temp12) cerr<<",";
            cerr<<e; ++cnt_temp12;
    }cerr<<"}";
}
template<typename T>
void _print(T x) {cerr<<x;}

void dbg() {cerr<<endl;}
template<typename Head,typename... Tail>
void dbg(Head H,Tail... T) {
    _print(H);
    if(sizeof...(T)) cerr<<",";
    else cerr<<" \"]";
    dbg(T...);
}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:[\" ",dbg(__VA_ARGS__)

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//int rnglr(int l,int r) {return rng()%(r-l+1)+l;}

struct dt {
    int x,y,idx;
    bool operator<(const dt &r) {
        return y<r.y;
    }
};

const int mxn = 2e5+100;
int n;
int flag[7][mxn];
vector<int> par;

int dm[4] = {-2,0,2,0};
int dn[4] = {0,2,0,-2};

bool valid(int M,int N) {
    if(M<2 or N<2 or M>4) return false;
    return flag[M][N]>=0;
}

int findp(int x) {
    if(par[x] == x) return x;
    return par[x] = findp(par[x]);
}

void unionset(int u,int v) {
    int U = findp(u), V = findp(v);
    par[U] = V;
}

int construct_roads(std::vector<int> x, std::vector<int> y) {
    if (x.size() == 1) {
        build({}, {}, {}, {});
        return 1;
    }

    n = x.size();
    par.resize(n);
    for(int i=0;i<n;i++) par[i] = i;
    vector<dt> ar;
    for(int i=0;i<7;i++) fill(flag[i],flag[i]+mxn,-1);

    for(int i=0;i<n;i++) {
        ar.push_back({x[i],y[i],i});
    }
    sort(all(ar));

    for(int i=0;i<n;i++) {
        flag[ar[i].x][ar[i].y] = i;
    }

    vector<int> u,v,a,b;

    for(int i=0;i<n;i++) {

        int X = ar[i].x, Y = ar[i].y;
        for(int j=0;j<4;j++) {
            int XX = X+dm[j], YY = Y+dn[j];
            if(valid(XX,YY)) {
                int i2 = flag[XX][YY];
                assert(ar[i2].x == XX && ar[i2].y == YY);
                if(i>i2) continue;
//                debug(i,i2);
                u.push_back(ar[i].idx);
                v.push_back(ar[i2].idx);
                unionset(i,i2);

                if(X==2) {
                    if(XX==2) a.push_back(1),b.push_back(min(Y,YY)+1);
                    else a.push_back(3),b.push_back(min(Y,YY)+1);
                }
                else {
                    // X=4
                    if(XX==2) a.push_back(3),b.push_back(min(Y,YY)+1);
                    else a.push_back(5), b.push_back(min(Y,YY)+1);
                }
            }
//            debug(u);
//            debug(v);
//            debug(a);
//            debug(b);
        }
    }
//    debug(u);
//    debug(v);
//    debug(a);
//    debug(b);

    set<int> par_list;
    for(int i=0;i<n;i++) {
        int temp = findp(i);
        par_list.insert(temp);
    }
    if(par_list.size()!=1) return 0;
    build(u,v,a,b);
    return 1;
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 4 ms 5708 KB Output is correct
3 Correct 4 ms 5708 KB Output is correct
4 Correct 4 ms 5708 KB Output is correct
5 Correct 4 ms 5708 KB Output is correct
6 Correct 3 ms 5708 KB Output is correct
7 Correct 3 ms 5708 KB Output is correct
8 Correct 4 ms 5708 KB Output is correct
9 Correct 74 ms 15168 KB Output is correct
10 Correct 10 ms 6812 KB Output is correct
11 Correct 36 ms 10644 KB Output is correct
12 Correct 14 ms 7192 KB Output is correct
13 Correct 16 ms 8724 KB Output is correct
14 Correct 4 ms 5708 KB Output is correct
15 Correct 4 ms 5836 KB Output is correct
16 Correct 74 ms 15076 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 4 ms 5708 KB Output is correct
3 Correct 4 ms 5708 KB Output is correct
4 Correct 4 ms 5708 KB Output is correct
5 Correct 4 ms 5708 KB Output is correct
6 Correct 3 ms 5708 KB Output is correct
7 Correct 3 ms 5708 KB Output is correct
8 Correct 4 ms 5708 KB Output is correct
9 Correct 74 ms 15168 KB Output is correct
10 Correct 10 ms 6812 KB Output is correct
11 Correct 36 ms 10644 KB Output is correct
12 Correct 14 ms 7192 KB Output is correct
13 Correct 16 ms 8724 KB Output is correct
14 Correct 4 ms 5708 KB Output is correct
15 Correct 4 ms 5836 KB Output is correct
16 Correct 74 ms 15076 KB Output is correct
17 Correct 3 ms 5708 KB Output is correct
18 Correct 3 ms 5708 KB Output is correct
19 Correct 3 ms 5708 KB Output is correct
20 Correct 3 ms 5708 KB Output is correct
21 Correct 3 ms 5756 KB Output is correct
22 Correct 4 ms 5708 KB Output is correct
23 Correct 183 ms 29252 KB Output is correct
24 Correct 4 ms 5708 KB Output is correct
25 Correct 5 ms 5836 KB Output is correct
26 Correct 4 ms 5964 KB Output is correct
27 Correct 5 ms 5964 KB Output is correct
28 Correct 73 ms 15256 KB Output is correct
29 Correct 110 ms 19388 KB Output is correct
30 Correct 151 ms 25276 KB Output is correct
31 Correct 206 ms 29116 KB Output is correct
32 Correct 4 ms 5708 KB Output is correct
33 Correct 3 ms 5708 KB Output is correct
34 Correct 4 ms 5708 KB Output is correct
35 Correct 3 ms 5708 KB Output is correct
36 Correct 3 ms 5708 KB Output is correct
37 Correct 3 ms 5708 KB Output is correct
38 Correct 3 ms 5708 KB Output is correct
39 Correct 4 ms 5708 KB Output is correct
40 Correct 3 ms 5708 KB Output is correct
41 Correct 4 ms 5708 KB Output is correct
42 Correct 3 ms 5708 KB Output is correct
43 Correct 5 ms 5836 KB Output is correct
44 Correct 6 ms 5964 KB Output is correct
45 Correct 102 ms 14856 KB Output is correct
46 Correct 106 ms 19916 KB Output is correct
47 Correct 106 ms 19860 KB Output is correct

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 4 ms 5708 KB Output is correct
3 Correct 4 ms 5708 KB Output is correct
4 Correct 4 ms 5708 KB Output is correct
5 Correct 4 ms 5708 KB Output is correct
6 Correct 3 ms 5708 KB Output is correct
7 Correct 3 ms 5708 KB Output is correct
8 Correct 4 ms 5708 KB Output is correct
9 Correct 74 ms 15168 KB Output is correct
10 Correct 10 ms 6812 KB Output is correct
11 Correct 36 ms 10644 KB Output is correct
12 Correct 14 ms 7192 KB Output is correct
13 Correct 16 ms 8724 KB Output is correct
14 Correct 4 ms 5708 KB Output is correct
15 Correct 4 ms 5836 KB Output is correct
16 Correct 74 ms 15076 KB Output is correct
17 Correct 3 ms 5708 KB Output is correct
18 Correct 3 ms 5708 KB Output is correct
19 Correct 3 ms 5708 KB Output is correct
20 Correct 3 ms 5708 KB Output is correct
21 Correct 3 ms 5756 KB Output is correct
22 Correct 4 ms 5708 KB Output is correct
23 Correct 183 ms 29252 KB Output is correct
24 Correct 4 ms 5708 KB Output is correct
25 Correct 5 ms 5836 KB Output is correct
26 Correct 4 ms 5964 KB Output is correct
27 Correct 5 ms 5964 KB Output is correct
28 Correct 73 ms 15256 KB Output is correct
29 Correct 110 ms 19388 KB Output is correct
30 Correct 151 ms 25276 KB Output is correct
31 Correct 206 ms 29116 KB Output is correct
32 Correct 4 ms 5708 KB Output is correct
33 Correct 3 ms 5708 KB Output is correct
34 Correct 4 ms 5708 KB Output is correct
35 Correct 3 ms 5708 KB Output is correct
36 Correct 3 ms 5708 KB Output is correct
37 Correct 3 ms 5708 KB Output is correct
38 Correct 3 ms 5708 KB Output is correct
39 Correct 4 ms 5708 KB Output is correct
40 Correct 3 ms 5708 KB Output is correct
41 Correct 4 ms 5708 KB Output is correct
42 Correct 3 ms 5708 KB Output is correct
43 Correct 5 ms 5836 KB Output is correct
44 Correct 6 ms 5964 KB Output is correct
45 Correct 102 ms 14856 KB Output is correct
46 Correct 106 ms 19916 KB Output is correct
47 Correct 106 ms 19860 KB Output is correct
48 Incorrect 4 ms 5708 KB Tree @(5, 3) appears more than once: for edges on positions 0 and 1
49 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 4 ms 5708 KB Output is correct
3 Correct 4 ms 5708 KB Output is correct
4 Correct 4 ms 5708 KB Output is correct
5 Correct 4 ms 5708 KB Output is correct
6 Correct 3 ms 5708 KB Output is correct
7 Correct 3 ms 5708 KB Output is correct
8 Correct 4 ms 5708 KB Output is correct
9 Correct 74 ms 15168 KB Output is correct
10 Correct 10 ms 6812 KB Output is correct
11 Correct 36 ms 10644 KB Output is correct
12 Correct 14 ms 7192 KB Output is correct
13 Correct 16 ms 8724 KB Output is correct
14 Correct 4 ms 5708 KB Output is correct
15 Correct 4 ms 5836 KB Output is correct
16 Correct 74 ms 15076 KB Output is correct
17 Runtime error 10 ms 11428 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 4 ms 5708 KB Output is correct
3 Correct 4 ms 5708 KB Output is correct
4 Correct 4 ms 5708 KB Output is correct
5 Correct 4 ms 5708 KB Output is correct
6 Correct 3 ms 5708 KB Output is correct
7 Correct 3 ms 5708 KB Output is correct
8 Correct 4 ms 5708 KB Output is correct
9 Correct 74 ms 15168 KB Output is correct
10 Correct 10 ms 6812 KB Output is correct
11 Correct 36 ms 10644 KB Output is correct
12 Correct 14 ms 7192 KB Output is correct
13 Correct 16 ms 8724 KB Output is correct
14 Correct 4 ms 5708 KB Output is correct
15 Correct 4 ms 5836 KB Output is correct
16 Correct 74 ms 15076 KB Output is correct
17 Runtime error 80 ms 24392 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 4 ms 5708 KB Output is correct
3 Correct 4 ms 5708 KB Output is correct
4 Correct 4 ms 5708 KB Output is correct
5 Correct 4 ms 5708 KB Output is correct
6 Correct 3 ms 5708 KB Output is correct
7 Correct 3 ms 5708 KB Output is correct
8 Correct 4 ms 5708 KB Output is correct
9 Correct 74 ms 15168 KB Output is correct
10 Correct 10 ms 6812 KB Output is correct
11 Correct 36 ms 10644 KB Output is correct
12 Correct 14 ms 7192 KB Output is correct
13 Correct 16 ms 8724 KB Output is correct
14 Correct 4 ms 5708 KB Output is correct
15 Correct 4 ms 5836 KB Output is correct
16 Correct 74 ms 15076 KB Output is correct
17 Correct 3 ms 5708 KB Output is correct
18 Correct 3 ms 5708 KB Output is correct
19 Correct 3 ms 5708 KB Output is correct
20 Correct 3 ms 5708 KB Output is correct
21 Correct 3 ms 5756 KB Output is correct
22 Correct 4 ms 5708 KB Output is correct
23 Correct 183 ms 29252 KB Output is correct
24 Correct 4 ms 5708 KB Output is correct
25 Correct 5 ms 5836 KB Output is correct
26 Correct 4 ms 5964 KB Output is correct
27 Correct 5 ms 5964 KB Output is correct
28 Correct 73 ms 15256 KB Output is correct
29 Correct 110 ms 19388 KB Output is correct
30 Correct 151 ms 25276 KB Output is correct
31 Correct 206 ms 29116 KB Output is correct
32 Correct 4 ms 5708 KB Output is correct
33 Correct 3 ms 5708 KB Output is correct
34 Correct 4 ms 5708 KB Output is correct
35 Correct 3 ms 5708 KB Output is correct
36 Correct 3 ms 5708 KB Output is correct
37 Correct 3 ms 5708 KB Output is correct
38 Correct 3 ms 5708 KB Output is correct
39 Correct 4 ms 5708 KB Output is correct
40 Correct 3 ms 5708 KB Output is correct
41 Correct 4 ms 5708 KB Output is correct
42 Correct 3 ms 5708 KB Output is correct
43 Correct 5 ms 5836 KB Output is correct
44 Correct 6 ms 5964 KB Output is correct
45 Correct 102 ms 14856 KB Output is correct
46 Correct 106 ms 19916 KB Output is correct
47 Correct 106 ms 19860 KB Output is correct
48 Incorrect 4 ms 5708 KB Tree @(5, 3) appears more than once: for edges on positions 0 and 1
49 Halted 0 ms 0 KB -