oj.uz

Submission #1024261

# Submission time Handle Problem Language Result Execution time Memory
1024261 2024-07-15T20:45:16 Z Abito Fountain Parks (IOI21_parks) C++17
5 / 100
 162 ms 50504 KB 
#include "parks.h"
#include <bits/stdc++.h>
#define pb push_back
#define ep insert
#define F first
#define S second
using namespace std;
const int N=2e5+5;
int a[N],b[N],par[N],sz[N],n;
vector<int> c[N],r[N];
vector<int> adj[N];
bool cmp(int x,int y){
    return a[x]<a[y];
}
bool cmp2(int x,int y){
    return b[x]>b[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);
        r[x[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){
                if (getpar(c[i][j])==getpar(c[i+2][idx])) continue;
                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);
            }
        }
    }
    //for (int i=0;i<U.size();i++) cout<<U[i]<<' '<<V[i]<<endl;
    if (sz[getpar(0)]!=n) return 0;
    //for (int i=0;i<N;i+=2) sort(r[i].begin(),r[i].end(),cmp2);
    vector<int> d(U.size()),e(U.size());
    set<pair<int,int>> bench;
    bool h=0;
    int last=-1;
    for (int i=0;i<U.size();i++){
        if (s[i]==0) continue;
        if (a[U[i]]!=last){
            last=a[U[i]];
            if (a[U[i]]%4==2) h=1;
            else h=0;
        }
        if (!h){
            d[i]=a[U[i]]-1;
            e[i]=b[U[i]]-1;
            bench.ep({d[i],e[i]});
            h=!h;
        }
        else{
            d[i]=a[U[i]]+1;
            e[i]=b[U[i]]-1;
            bench.ep({d[i],e[i]});
            h=!h;
        }
    }
    //for (auto u:bench) cout<<u.F<<' '<<u.S<<endl;
    for (int i=0;i<U.size();i++){
        if (s[i]==2) continue;
        int xx=a[U[i]]+1,yy=b[U[i]]-1;
        if (!bench.count({xx,yy})){
            d[i]=xx;
            e[i]=yy;
            bench.ep({xx,yy});
            continue;
        }
        yy+=2;
        d[i]=xx;
        e[i]=yy;
        bench.ep({xx,yy});
    }
    build(U,V,d,e);
    return 1;
}

Compilation message

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14936 KB Output is correct
2 Correct 3 ms 16988 KB Output is correct
3 Correct 3 ms 16988 KB Output is correct
4 Correct 3 ms 16988 KB Output is correct
5 Correct 3 ms 16988 KB Output is correct
6 Correct 3 ms 16988 KB Output is correct
7 Correct 3 ms 16988 KB Output is correct
8 Correct 3 ms 16988 KB Output is correct
9 Correct 68 ms 35256 KB Output is correct
10 Correct 8 ms 18780 KB Output is correct
11 Correct 36 ms 26840 KB Output is correct
12 Correct 11 ms 19804 KB Output is correct
13 Correct 12 ms 21208 KB Output is correct
14 Correct 3 ms 17000 KB Output is correct
15 Correct 3 ms 16988 KB Output is correct
16 Correct 70 ms 35272 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14936 KB Output is correct
2 Correct 3 ms 16988 KB Output is correct
3 Correct 3 ms 16988 KB Output is correct
4 Correct 3 ms 16988 KB Output is correct
5 Correct 3 ms 16988 KB Output is correct
6 Correct 3 ms 16988 KB Output is correct
7 Correct 3 ms 16988 KB Output is correct
8 Correct 3 ms 16988 KB Output is correct
9 Correct 68 ms 35256 KB Output is correct
10 Correct 8 ms 18780 KB Output is correct
11 Correct 36 ms 26840 KB Output is correct
12 Correct 11 ms 19804 KB Output is correct
13 Correct 12 ms 21208 KB Output is correct
14 Correct 3 ms 17000 KB Output is correct
15 Correct 3 ms 16988 KB Output is correct
16 Correct 70 ms 35272 KB Output is correct
17 Correct 3 ms 16984 KB Output is correct
18 Correct 3 ms 16836 KB Output is correct
19 Correct 4 ms 16828 KB Output is correct
20 Incorrect 3 ms 16984 KB Tree @(3, 7) appears more than once: for edges on positions 2 and 4
21 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14936 KB Output is correct
2 Correct 3 ms 16988 KB Output is correct
3 Correct 3 ms 16988 KB Output is correct
4 Correct 3 ms 16988 KB Output is correct
5 Correct 3 ms 16988 KB Output is correct
6 Correct 3 ms 16988 KB Output is correct
7 Correct 3 ms 16988 KB Output is correct
8 Correct 3 ms 16988 KB Output is correct
9 Correct 68 ms 35256 KB Output is correct
10 Correct 8 ms 18780 KB Output is correct
11 Correct 36 ms 26840 KB Output is correct
12 Correct 11 ms 19804 KB Output is correct
13 Correct 12 ms 21208 KB Output is correct
14 Correct 3 ms 17000 KB Output is correct
15 Correct 3 ms 16988 KB Output is correct
16 Correct 70 ms 35272 KB Output is correct
17 Correct 3 ms 16984 KB Output is correct
18 Correct 3 ms 16836 KB Output is correct
19 Correct 4 ms 16828 KB Output is correct
20 Incorrect 3 ms 16984 KB Tree @(3, 7) appears more than once: for edges on positions 2 and 4
21 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14936 KB Output is correct
2 Correct 3 ms 16988 KB Output is correct
3 Correct 3 ms 16988 KB Output is correct
4 Correct 3 ms 16988 KB Output is correct
5 Correct 3 ms 16988 KB Output is correct
6 Correct 3 ms 16988 KB Output is correct
7 Correct 3 ms 16988 KB Output is correct
8 Correct 3 ms 16988 KB Output is correct
9 Correct 68 ms 35256 KB Output is correct
10 Correct 8 ms 18780 KB Output is correct
11 Correct 36 ms 26840 KB Output is correct
12 Correct 11 ms 19804 KB Output is correct
13 Correct 12 ms 21208 KB Output is correct
14 Correct 3 ms 17000 KB Output is correct
15 Correct 3 ms 16988 KB Output is correct
16 Correct 70 ms 35272 KB Output is correct
17 Correct 3 ms 16988 KB Output is correct
18 Correct 3 ms 16988 KB Output is correct
19 Correct 3 ms 16988 KB Output is correct
20 Incorrect 161 ms 50504 KB Tree @(7, 199997) appears more than once: for edges on positions 99996 and 100000
21 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14936 KB Output is correct
2 Correct 3 ms 16988 KB Output is correct
3 Correct 3 ms 16988 KB Output is correct
4 Correct 3 ms 16988 KB Output is correct
5 Correct 3 ms 16988 KB Output is correct
6 Correct 3 ms 16988 KB Output is correct
7 Correct 3 ms 16988 KB Output is correct
8 Correct 3 ms 16988 KB Output is correct
9 Correct 68 ms 35256 KB Output is correct
10 Correct 8 ms 18780 KB Output is correct
11 Correct 36 ms 26840 KB Output is correct
12 Correct 11 ms 19804 KB Output is correct
13 Correct 12 ms 21208 KB Output is correct
14 Correct 3 ms 17000 KB Output is correct
15 Correct 3 ms 16988 KB Output is correct
16 Correct 70 ms 35272 KB Output is correct
17 Correct 162 ms 50356 KB Output is correct
18 Incorrect 152 ms 50484 KB Tree @(50003, 50003) appears more than once: for edges on positions 50000 and 149998
19 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14936 KB Output is correct
2 Correct 3 ms 16988 KB Output is correct
3 Correct 3 ms 16988 KB Output is correct
4 Correct 3 ms 16988 KB Output is correct
5 Correct 3 ms 16988 KB Output is correct
6 Correct 3 ms 16988 KB Output is correct
7 Correct 3 ms 16988 KB Output is correct
8 Correct 3 ms 16988 KB Output is correct
9 Correct 68 ms 35256 KB Output is correct
10 Correct 8 ms 18780 KB Output is correct
11 Correct 36 ms 26840 KB Output is correct
12 Correct 11 ms 19804 KB Output is correct
13 Correct 12 ms 21208 KB Output is correct
14 Correct 3 ms 17000 KB Output is correct
15 Correct 3 ms 16988 KB Output is correct
16 Correct 70 ms 35272 KB Output is correct
17 Correct 3 ms 16984 KB Output is correct
18 Correct 3 ms 16836 KB Output is correct
19 Correct 4 ms 16828 KB Output is correct
20 Incorrect 3 ms 16984 KB Tree @(3, 7) appears more than once: for edges on positions 2 and 4
21 Halted 0 ms 0 KB -