Submission #629778

#	Time	Username	Problem	Language	Result	Execution time	Memory
629778		Cross_Ratio	Fountain Parks (IOI21_parks)	C++17	5 / 100	623 ms	51240 KiB

parks

#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
void build(vector<int>,vector<int>,vector<int>,vector<int>);
int X[200005];
int Y[200005];
typedef pair<int,int> P;
int N;
map<P,int> M;
vector<vector<int>> adj;
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
struct UnionFind {
    vector<int> root;
    UnionFind(int N) {
        root.resize(N);
        fill(root.begin(),root.end(),-1);
    }
    int Find(int n) {
        if(root[n]<0) return n;
        int r = Find(root[n]);
        root[n] = r;
        return r;
    }
    void Merge(int x, int y) {
        x = Find(x), y = Find(y);
        if(x==y) return;
        if(root[x]>root[y]) swap(x, y);
        root[x] += root[y];
        root[y] = x;
    }
};
vector<P> Edge;
const int INF = 1e8;
int dm[2] = {1,-1};
int construct_roads(vector<int> _X, vector<int> _Y) {
    N = _X.size();
    int i, j;
    for(i=0;i<N;i++) {
        X[i] = _X[i];
        Y[i] = _Y[i];
        M[P(X[i],Y[i])] = i;
    }
    adj.resize(N);
    for(i=0;i<N;i++) {
        for(j=0;j<4;j++) {
            int x = X[i] + 2*dx[j];
            int y = Y[i] + 2*dy[j];
            if(M.count(P(x,y))) {
                int id = M[P(x,y)];
                adj[id].push_back(i);
                adj[i].push_back(id);
                Edge.push_back(P(i,id));
            }
        }
    }
    vector<P> Tree;
    UnionFind UF(N);
    for(i=0;i<Edge.size();i++) {
        if(UF.Find(Edge[i].first) != UF.Find(Edge[i].second)) {
            Tree.push_back(Edge[i]);
            UF.Merge(Edge[i].first, Edge[i].second);
        }
    }
    for(i=0;i<N;i++) {
        if(UF.Find(0)!=UF.Find(i)) return 0;
    }
    vector<int> A, B;
    for(i=0;i<Tree.size();i++) {
        int x1 = X[Tree[i].first];
        int y1 = Y[Tree[i].first];
        int x2 = X[Tree[i].second];
        int y2 = Y[Tree[i].second];
        //cout << x1 << ' ' << x2 << ' ' << y1 << ' ' << y2 << '\n';
        if(x1==x2) {
            int x = x1;
            int y = (y1+y2)/2;
            for(j=0;j<1;j++) {
                int x3 = x + dm[j];
                if(true) {
                    A.push_back(x3);
                    B.push_back(y);
                    //cout << "push1\n";
                }
            }
        }
        if(y1==y2) {
            int x = (x1+x2)/2;
            int y = y2;
            for(j=0;j<2;j++) {
                int y3 = y + dm[j];
                if(1==y3%4) {
                    A.push_back(x);
                    B.push_back(y3);
                    //cout << "push2\n";
                }
            }
        }
    }
    vector<int> U, V;
    for(i=0;i<Tree.size();i++) {
        U.push_back(Tree[i].first);
        V.push_back(Tree[i].second);
    }
    /*for(i=0;i<U.size();i++) cout <<U[i] << ' ';
    cout << '\n';
    for(i=0;i<V.size();i++) cout << V[i] << ' ';
    cout << '\n';
    for(i=0;i<A.size();i++)cout <<A[i] << ' ';
    cout << '\n';
    for(i=0;i<B.size();i++) cout << B[i] <<' ';
    cout << '\n';*/
    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:59:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for(i=0;i<Edge.size();i++) {
      |             ~^~~~~~~~~~~~
parks.cpp:69:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |     for(i=0;i<Tree.size();i++) {
      |             ~^~~~~~~~~~~~
parks.cpp:101:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |     for(i=0;i<Tree.size();i++) {
      |             ~^~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30