oj.uz

Submission #436722

# Submission time Handle Problem Language Result Execution time Memory
436722 2021-06-24T19:45:39 Z David_M Fountain Parks (IOI21_parks) C++17
0 / 100
 10 ms 14412 KB 
#include "parks.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define F first
#define S second

map <pair<int, int>, int> m;
int ff[600010], f[600010], fff[200010], n, L[400010], D[400010], e;
vector<int> A1, A2, A3, A4, v[600010], xx, yy;
pair<int, int> t[600010], W[400010];

void Ans(int x, int y){
    if(f[x] || f[y])return;
    f[x]=f[y]=1;
    if(x>y)swap(x, y);
    if(x<n)A1.pb( x ), A2.pb( L[x] );
    else   A1.pb(x-n), A2.pb(D[x-n]);
    A3.pb(t[y].F),
    A4.pb(t[y].S);
}

void dfs(int x){
    ff[x]=1;
    if(x<=2*n)fff[W[x].F]=fff[W[x].S]=1;
    for(auto y:v[x]){
        if(ff[y])continue;
        Ans(x,y);
        dfs(y);
    }
}

int construct_roads(vector<int> x, vector<int> y) {

    for (auto i:x)xx.pb(i);
    for (auto i:y)yy.pb(i);

    n=x.size();
    int o=2*n;

    for (int i=1; i<=n; i++)m[{x[i-1], y[i-1]}]=i;
    for (int i=1; i<=n; i++){
        int X=x[i-1], Y=y[i-1];
        if(m[{X, Y-2}]){
            W[i]={i, m[{X, Y-2}]};
            L[i]=m[{X, Y-2}];
            if(!m[{X-1, Y-1}])t[++o]={X-1, Y-1}, m[{X-1, Y-1}]=o;
            e=m[{X-1, Y-1}];
            v[e].pb(i);
            v[i].pb(e);
            if(!m[{X+1, Y-1}])t[++o]={X+1, Y-1}, m[{X+1, Y-1}]=o;
            e=m[{X+1, Y-1}];
            v[e].pb(i);
            v[i].pb(e);
        }
        if(m[{X-2, Y}]){
            W[i+n]={i, m[{X-2, Y}]};
            D[i]=m[{X-2, Y}];
            if(!m[{X-1, Y-1}])t[++o]={X-1, Y-1}, m[{X-1, Y-1}]=o;
            e=m[{X-1, Y-1}];
            v[e].pb(i+n);
            v[i+n].pb(e);
            if(!m[{X-1, Y+1}])t[++o]={X-1, Y+1}, m[{X-1, Y+1}]=o;
            e=m[{X-1, Y+1}];
            v[e].pb(i+n);
            v[i+n].pb(e);
        }
    }

    dfs(1);
    for(int i=1; i<=n; i++)if(!fff[i])return 0;

    build(A1, A2, A3, A4);
    return 1;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 14412 KB Solution announced impossible, but it is possible.
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 14412 KB Solution announced impossible, but it is possible.
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 14412 KB Solution announced impossible, but it is possible.
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 14412 KB Solution announced impossible, but it is possible.
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 14412 KB Solution announced impossible, but it is possible.
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 14412 KB Solution announced impossible, but it is possible.
2 Halted 0 ms 0 KB -