oj.uz

답안 #788439

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
788439 2023-07-20T08:39:05 Z alexander707070 분수 공원 (IOI21_parks) C++17
0 / 100
 1 ms 212 KB 
#include<bits/stdc++.h>
#include "parks.h"
#define MAXN 200007
using namespace std;

struct bench{
    int from,to;
    int a,b;
};

int L,M,R;
int n,dsu[MAXN],up[MAXN],down[MAXN],curr;
vector< pair<int,int> > l,m,r;
vector<bench> sol;
vector<int> A,B,C,D;

int root(int x){
    if(dsu[x]==x)return x;
    dsu[x]=root(dsu[x]);
    return dsu[x];
}

void mergev(int x,int y){
    dsu[root(x)]=root(y);
}

int construct_roads(vector<int> x,vector<int> y){
    n=int(x.size());

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

        if(x[i]==2){
            l.push_back({y[i],i});
            down[y[i]]=i+1;
        }
        if(x[i]==4)m.push_back({y[i],i});
        if(x[i]==6){
            r.push_back({y[i],i});
            up[y[i]]=i+1;
        }
    }

    sort(l.begin(),l.end());
    sort(m.begin(),m.end());
    sort(r.begin(),r.end());

    L=int(l.size()); M=int(m.size()); R=int(r.size());

    for(int i=0;i<L-1;i++){
        if(l[i].first+2==l[i+1].first){
            mergev(l[i].second,l[i+1].second);
            sol.push_back({l[i].second,l[i+1].second,1,l[i].first+1});
        }
    }

    for(int i=0;i<R-1;i++){
        if(r[i].first+2==r[i+1].first){
            mergev(r[i].second,r[i+1].second);
            sol.push_back({r[i].second,r[i+1].second,7,r[i].first+1});
        }
    }

    for(int i=0;i<M-1;i++){
        if(m[i].first+2==m[i+1].first){
            mergev(m[i].second,m[i+1].second);
            if(m[i].first%4==0)sol.push_back({m[i].second,m[i+1].second,3,m[i].first+1});
            if(m[i].first%4==2)sol.push_back({m[i].second,m[i+1].second,5,m[i].first+1});
        }
    }

    for(int i=0;i<M;i++){
        if(down[m[i].first]!=0){
            curr=down[m[i].first]-1;
            if(root(curr)==root(m[i].second))continue;

            mergev(curr,m[i].second);
            if(m[i].first%4==0)sol.push_back({curr,m[i].second,3,m[i].first-1});
            if(m[i].first%4==2)sol.push_back({curr,m[i].second,3,m[i].first+1});
        }
    }

    for(int i=0;i<M;i++){
        if(up[m[i].first]!=0){
            curr=up[m[i].first]-1;
            if(root(curr)==root(m[i].second))continue;

            mergev(curr,m[i].second);
            if(m[i].first%4==0)sol.push_back({m[i].second,curr,5,m[i].first+1});
            if(m[i].first%4==2)sol.push_back({m[i].second,curr,5,m[i].first-1});
        }
    }

    return 0;

    for(int i=0;i<n;i++){
        if(root(i)!=root(0))return 0;
    }

    for(int i=0;i<sol.size();i++){
        A.push_back(sol[i].from);
        B.push_back(sol[i].to);
        C.push_back(sol[i].a);
        D.push_back(sol[i].b);
    }

    build(A,B,C,D);
}

/*
int main(){
    construct_roads({4, 4, 6, 4, 2}, {4, 6, 4, 2, 4});
}
*/

Compilation message

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:100:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bench>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |     for(int i=0;i<sol.size();i++){
      |                 ~^~~~~~~~~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Solution announced impossible, but it is possible.
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Solution announced impossible, but it is possible.
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Solution announced impossible, but it is possible.
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Solution announced impossible, but it is possible.
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Solution announced impossible, but it is possible.
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Solution announced impossible, but it is possible.
2 Halted 0 ms 0 KB -