Submission #1239344

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239344		Hamed_Ghaffari	Fountain Parks (IOI21_parks)	C++20	Compilation error	0 ms	0 KiB

parks

#include "parks.h"
#include <bits/stdc++.h>
using namespace std;

using pii = pair<int, int>;

#define X first
#define Y second

const int MXN = 2e5+5;

namespace two_sat {
    int n, cmp[MXN<<1];
    bool vis[MXN<<1];
    vector<int> g[MXN<<1], gr[MXN<<1], ord;
    inline void add_edge(int u, int v) {
        g[u].push_back(v);
        gr[v].push_back(u);
    }
    inline void add(int u, bool nu, int v, bool nv) {
        add_edge(2*u+1-nu, 2*v+nv);
        add_edge(2*v+1-nv, 2*u+nu);
    }
    void dfs(int v) {
        vis[v] = 1;
        for(int u : g[v])
            if(!vis[u])
                dfs(u);
        ord.push_back(v);
    }
    void dfsr(int v, int c) {
        cmp[v] = c;
        for(int u : gr[v])
            if(!cmp[u])
                dfsr(u, c);
    }
    bool solve(vector<bool> &ans) {
        for(int i=0; i<2*n; i++)
            if(!vis[i])
                dfs(i);
        int c=0;
        while(!ord.empty()) {
            int v = ord.back();
            ord.pop_back();
            if(!cmp[v]) dfsr(v, ++c);
        }
        for(int i=0; i<n; i++)
            if(cmp[2*i]==cmp[2*i+1]) return 0;
            else ans[i] = (cmp[2*i+1]>cmp[2*i]);
        return 1;
    }
}

int n, ord[MXN], dsu[MXN];
pii P[MXN];

int find(int v) { return v==dsu[v] ? v : dsu[v] = find(dsu[v]); };
inline void merge(int u, int v) { dsu[find(v)] = find(u); }

inline int id(pii p) {
    int pos = lower_bound(P, P+n, p)-P;
    return pos<n && P[pos]==p ? ord[pos] : -1;
}

int construct_roads(vector<int> x, vector<int> y) {
    n = x.size();
    iota(ord, ord+n, 0);
    sort(ord, ord+n, [&](int i, int j) {
        return x[i]+y[i]<x[j]+y[j] || (x[i]+y[i]==x[j]+y[j] && x[i]<x[j]);
    });
    for(int i=0; i<n; i++) P[i] = pii(x[ord[i]], y[ord[i]]);
    iota(dsu, dsu+n, 0);
    vector<int> U, V;
    for(int i=0; i<n; i++) {
        int j = id(pii(x[i], y[i]-2));
        if(j!=-1 && find(i)!=find(j)) {
            U.push_back(i);
            V.push_back(j);
            merge(i, j);
        }
        int j = id(pii(x[i]-2, y[i]));
        if(j!=-1 && find(i)!=find(j)) {
            U.push_back(i);
            V.push_back(j);
            merge(i, j);
        }
    }
    if(U.size()!=n-1) return 0;
    two_sat::n = n-1;
    map<pii, vector<pair<int, bool>>> mp;
    for(int i=0; i<n-1; i++)
        if(x[U[i]]==x[V[i]])
            mp[{x[U[i]]-1, (y[U[i]]+y[V[i]])>>1}].push_back({i, 0}),
            mp[{x[U[i]]+1, (y[U[i]]+y[V[i]])>>1}].push_back({i, 1});
        else
            mp[{(x[U[i]]+x[V[i]])>>1, y[U[i]]-1}].push_back({i, 0}),
            mp[{(x[U[i]]+x[V[i]])>>1, y[U[i]]+1}].push_back({i, 1});
    for(auto tmp : mp)
        for(int i=0; i<tmp.Y.size(); i++)
            for(int j=0; j<tmp.Y.size(); j++)
                if(i^j)
                    two_sat::add(tmp.Y[i].X, tmp.Y[i].Y^1, tmp.Y[j].X, tmp.Y[j].Y^1);
    vector<bool> ans(n-1);
    if(!two_sat::solve(ans)) return 0;
    vector<int> A(n-1), B(n-1);
    for(int i=0; i<n-1; i++)
        if(x[U[i]]==x[V[i]]) {
            if(ans[i]) A[i] = x[U[i]]+1, B[i] = (y[U[i]]+y[V[i]])>>1;
            else       A[i] = x[U[i]]-1, B[i] = (y[U[i]]+y[V[i]])>>1;
        }
        else {
            if(ans[i]) A[i] = (x[U[i]]+x[V[i]])>>1, B[i] = y[U[i]]+1;
            else       A[i] = (x[U[i]]+x[V[i]])>>1, B[i] = y[U[i]]-1;
        }
    build(U, V, A, B);
    return 1;
}

Compilation message (stderr)

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:81:13: error: redeclaration of 'int j'
   81 |         int j = id(pii(x[i]-2, y[i]));
      |             ^
parks.cpp:75:13: note: 'int j' previously declared here
   75 |         int j = id(pii(x[i], y[i]-2));
      |             ^