oj.uz

답안 #1024249

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1024249 2024-07-15T19:54:34 Z Abito 분수 공원 (IOI21_parks) C++17
0 / 100
 2 ms 12892 KB 
#include "parks.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int N=2e5+5;
int a[N],b[N],par[N],sz[N],n;
vector<int> c[N];
vector<int> adj[N];
bool cmp(int x,int y){
    return a[x]<a[y];
}
int getpar(int x){
    if (x==par[x]) return x;
    return par[x]=getpar(par[x]);
}
void link(int x,int y){
    x=getpar(x);
    y=getpar(y);
    if (x==y) return;
    if (sz[x]>sz[y]) swap(x,y);
    sz[y]+=sz[x];
    par[x]=y;
    return;
}
int construct_roads(std::vector<int> x, std::vector<int> y) {
    if (x.size() == 1) {
	build({}, {}, {}, {});
        return 1;
    }
    n=x.size();
    for (int i=0;i<n;i++){
        par[i]=i;
        sz[i]=1;
        a[i]=x[i];
        b[i]=y[i];
        c[y[i]].pb(i);
    }
    vector<int> U,V,s;
    for (int i=0;i<N;i+=2) sort(c[i].begin(),c[i].end(),cmp);
    for (int i=0;i<N;i+=2){
        for (int j=0;j<int(c[i].size())-1;j++){
            if (a[c[i][j+1]]-a[c[i][j]]==2){
                link(c[i][j],c[i][j+1]);
                U.pb(c[i][j]);
                V.pb(c[i][j+1]);
                s.pb(0);
                adj[c[i][j]].pb(U.size()-1);
                adj[c[i][j+1]].pb(U.size()-1);
            }
        }
    }
    for (int i=N-1;i>=0;i--){
        for (int j=0;j<int(c[i].size());j++){
            int l=0,r=int(c[i+2].size())-1,mid,idx=-1;
            while (l<=r){
                mid=(l+r)/2;
                if (a[c[i+2][mid]]==a[c[i][j]]){
                    idx=mid;
                    break;
                }
                if (a[c[i+2][mid]]>a[c[i][j]]) r=mid-1;
                else l=mid+1;
            }
            if (idx!=-1){
                link(c[i][j],c[i+2][idx]);
                V.pb(c[i][j]);
                U.pb(c[i+2][idx]);
                s.pb(2);
                adj[c[i][j]].pb(U.size()-1);
                adj[c[i+2][idx]].pb(U.size()-1);
            }
        }
    }
    if (sz[getpar(0)]!=n) return 0;
    for (int i=0;i<U.size();i++){
        if (s[i]!=2) continue;
        int l=2,r=2,idxl=-1,idxr=-1;
        for (auto u:adj[V[i]]){
            int to=U[u];
            if (to==V[i]) to=V[u];
            if (a[to]==a[V[i]]) continue;
            if (a[to]>a[V[i]] && s[u]==0) r=0,idxr=u;
            if (a[to]<a[V[i]] && s[u]==0) l=0,idxl=u;
        }
        cout<<l<<' '<<r<<endl;
        for (auto u:adj[U[i]]){
            int to=U[u];
            if (to==U[i]) to=V[u];
            if (a[to]==a[U[i]]) continue;
            if (a[to]>a[U[i]] && s[u]==1) r=1,idxr=u;
            if (a[to]<a[U[i]] && s[u]==1) l=1,idxl=u;
        }
        cout<<U[i]<<' '<<V[i]<<' '<<l<<' '<<r<<' '<<idxl<<' '<<idxr<<endl;
        if (l==2 || r==2){
            //cout<<"c1"<<endl;
            if (r==2) s[i]=3;
            continue;
        }
        if (l==1){
            s[idxr]=1;
            s[i]=3;
            //cout<<"c2"<<endl;
            continue;
        }
        if (r==1){
            //cout<<"c3"<<endl;
            s[idxl]=1;
            continue;
        }
        s[idxr]=1;
        s[i]=3;
    }
    vector<int> d,e;
    for (int i=0;i<U.size();i++){
        if (s[i]==0){
            d.pb(a[U[i]]+1);
            e.pb(b[U[i]]+1);
            continue;
        }
        if (s[i]==1){
            d.pb(a[U[i]]+1);
            e.pb(b[U[i]]-1);
            continue;
        }
        if (s[i]==2){
            d.pb(a[U[i]]-1);
            e.pb(b[U[i]]-1);
            continue;
        }
        d.pb(a[U[i]]+1);
        e.pb(b[U[i]]-1);
        continue;
    }
    build(U,V,d,e);
    return 1;
}

Compilation message

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

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Incorrect 2 ms 12892 KB Possible tampering with the output
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Incorrect 2 ms 12892 KB Possible tampering with the output
3 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Incorrect 2 ms 12892 KB Possible tampering with the output
3 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Incorrect 2 ms 12892 KB Possible tampering with the output
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Incorrect 2 ms 12892 KB Possible tampering with the output
3 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Incorrect 2 ms 12892 KB Possible tampering with the output
3 Halted 0 ms 0 KB -