답안 #838477

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
838477	2023-08-27T07:31:07 Z	fatemetmhr	분수 공원 (IOI21_parks)	C++17	5 / 100	841 ms	73632 KB

parks

// Be Name Khoda //
 
//#pragma GCC optimize ("O3")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,O3")
 
#include "parks.h"
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
#define debug(x)  cerr << "(" << (#x) << "): " << (x) << endl;
#define all(x)    x.begin(), x.end()
#define MAX(x, y) ((x) > (y) ? (x) : (y))
#define MIN(x, y) ((x) < (y) ? (x) : (y))
#define fi        first
#define se        second
#define pb        push_back
#define mp        make_pair
 
const int maxn5 = 1e6 + 10;
 
 
int n;
vector <int> ret[2], ed[2];
map <pair<int, int>, int> av, cnt, idof;
set <pair<pair<int, int>, pair<int, int>>> rem;


void dfs(int v, int x, int y){
    av.erase(mp(x, y));
    if(av.find(mp(x - 2, y)) != av.end()){
        int u = av[mp(x - 2, y)];
        dfs(u, x - 2, y);
    }
    if(av.find(mp(x + 2, y)) != av.end()){
        int u = av[mp(x + 2, y)];
        dfs(u, x + 2, y);
    }
    if(av.find(mp(x, y - 2)) != av.end()){
        int u = av[mp(x, y - 2)];
        dfs(u, x, y - 2);
    }
    if(av.find(mp(x, y + 2)) != av.end()){
        int u = av[mp(x, y + 2)];
        dfs(u, x, y + 2);
    }
}
 
 
int construct_roads(std::vector<int> x, std::vector<int> y) {

    n = x.size();

    for(int i = 0; i < n; i++)
        av[mp(x[i], y[i])] = i;
    dfs(0, x[0], y[0]);
    if(av.size())
        return 0;

    for(int i = 0; i < n; i++){
        cnt[mp(x[i] - 1, y[i] - 1)]++;
        cnt[mp(x[i] + 1, y[i] - 1)]++;
        cnt[mp(x[i] - 1, y[i] + 1)]++;
        cnt[mp(x[i] + 1, y[i] + 1)]++;
        idof[mp(x[i], y[i])] = i;
    }


    for(auto it = cnt.begin(); it != cnt.end(); it++) if(it -> se == 4){
        int x = (it -> fi).fi, y = (it -> fi).se;
        x--; y--;
        if(((x / 2) + (y / 2)) % 2){ // is black
            rem.insert({{x, y}, {x + 2, y}});
        }
        else{ // is white
            rem.insert({{x, y}, {x, y + 2}});
        }
    }

    for(int i = 0; i < n; i++){
        if(idof.find(mp(x[i] + 2, y[i])) != idof.end() &&
            rem.find(mp(mp(x[i], y[i]), mp(x[i] + 2, y[i]))) == rem.end()){
            ed[0].pb(i);
            ed[1].pb(idof[mp(x[i] + 2, y[i])]);
            ret[0].pb(x[i] + 1);
            if(((x[i] / 2) + (y[i] / 2)) % 2)
                ret[1].pb(y[i] + 1);
            else
                ret[1].pb(y[i] - 1);
        }

        if(idof.find(mp(x[i], y[i] + 2)) != idof.end() &&
            rem.find(mp(mp(x[i], y[i]), mp(x[i], y[i] + 2))) == rem.end()){
            ed[0].pb(i);
            ed[1].pb(idof[mp(x[i], y[i] + 2)]);
            ret[1].pb(y[i] + 1);
            if(((x[i] / 2) + (y[i] / 2)) % 2)
                ret[0].pb(x[i] + 1);
            else
                ret[0].pb(x[i] - 1);
        }
    }

    build(ed[0], ed[1], ret[0], ret[1]);
    return 1;
}

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	300 KB	Output is correct
2	Correct	1 ms	304 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 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	296 ms	27460 KB	Output is correct
10	Correct	14 ms	3028 KB	Output is correct
11	Correct	100 ms	14276 KB	Output is correct
12	Correct	23 ms	4396 KB	Output is correct
13	Correct	21 ms	4008 KB	Output is correct
14	Correct	1 ms	300 KB	Output is correct
15	Correct	1 ms	468 KB	Output is correct
16	Correct	268 ms	33460 KB	Output is correct

Subtask #2
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	300 KB	Output is correct
2	Correct	1 ms	304 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 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	296 ms	27460 KB	Output is correct
10	Correct	14 ms	3028 KB	Output is correct
11	Correct	100 ms	14276 KB	Output is correct
12	Correct	23 ms	4396 KB	Output is correct
13	Correct	21 ms	4008 KB	Output is correct
14	Correct	1 ms	300 KB	Output is correct
15	Correct	1 ms	468 KB	Output is correct
16	Correct	268 ms	33460 KB	Output is correct
17	Correct	1 ms	300 KB	Output is correct
18	Incorrect	0 ms	212 KB	Tree @(3, 5) appears more than once: for edges on positions 0 and 1
19	Halted	0 ms	0 KB	-

Subtask #3
0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	300 KB	Output is correct
2	Correct	1 ms	304 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 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	296 ms	27460 KB	Output is correct
10	Correct	14 ms	3028 KB	Output is correct
11	Correct	100 ms	14276 KB	Output is correct
12	Correct	23 ms	4396 KB	Output is correct
13	Correct	21 ms	4008 KB	Output is correct
14	Correct	1 ms	300 KB	Output is correct
15	Correct	1 ms	468 KB	Output is correct
16	Correct	268 ms	33460 KB	Output is correct
17	Correct	1 ms	300 KB	Output is correct
18	Incorrect	0 ms	212 KB	Tree @(3, 5) appears more than once: for edges on positions 0 and 1
19	Halted	0 ms	0 KB	-

Subtask #4
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	300 KB	Output is correct
2	Correct	1 ms	304 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 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	296 ms	27460 KB	Output is correct
10	Correct	14 ms	3028 KB	Output is correct
11	Correct	100 ms	14276 KB	Output is correct
12	Correct	23 ms	4396 KB	Output is correct
13	Correct	21 ms	4008 KB	Output is correct
14	Correct	1 ms	300 KB	Output is correct
15	Correct	1 ms	468 KB	Output is correct
16	Correct	268 ms	33460 KB	Output is correct
17	Correct	0 ms	212 KB	Output is correct
18	Correct	1 ms	212 KB	Output is correct
19	Correct	0 ms	212 KB	Output is correct
20	Incorrect	841 ms	67524 KB	Tree @(192371, 7633) appears more than once: for edges on positions 0 and 1
21	Halted	0 ms	0 KB	-

Subtask #5
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	300 KB	Output is correct
2	Correct	1 ms	304 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 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	296 ms	27460 KB	Output is correct
10	Correct	14 ms	3028 KB	Output is correct
11	Correct	100 ms	14276 KB	Output is correct
12	Correct	23 ms	4396 KB	Output is correct
13	Correct	21 ms	4008 KB	Output is correct
14	Correct	1 ms	300 KB	Output is correct
15	Correct	1 ms	468 KB	Output is correct
16	Correct	268 ms	33460 KB	Output is correct
17	Incorrect	836 ms	73632 KB	Tree @(100001, 3) appears more than once: for edges on positions 31819 and 138412
18	Halted	0 ms	0 KB	-

Subtask #6
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	300 KB	Output is correct
2	Correct	1 ms	304 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 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	296 ms	27460 KB	Output is correct
10	Correct	14 ms	3028 KB	Output is correct
11	Correct	100 ms	14276 KB	Output is correct
12	Correct	23 ms	4396 KB	Output is correct
13	Correct	21 ms	4008 KB	Output is correct
14	Correct	1 ms	300 KB	Output is correct
15	Correct	1 ms	468 KB	Output is correct
16	Correct	268 ms	33460 KB	Output is correct
17	Correct	1 ms	300 KB	Output is correct
18	Incorrect	0 ms	212 KB	Tree @(3, 5) appears more than once: for edges on positions 0 and 1
19	Halted	0 ms	0 KB	-

답안 #838477

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 0 / 10.0

Subtask #3 0 / 15.0

Subtask #4 0 / 20.0

Subtask #5 0 / 20.0

Subtask #6 0 / 30.0

Subtask #1
5.0 / 5.0

Subtask #2
0 / 10.0

Subtask #3
0 / 15.0

Subtask #4
0 / 20.0

Subtask #5
0 / 20.0

Subtask #6
0 / 30.0