oj.uz

Submission #817844

# Submission time Handle Problem Language Result Execution time Memory
817844 2023-08-09T17:54:12 Z alvingogo Fountain Parks (IOI21_parks) C++17
5 / 100
 614 ms 46372 KB 
#include "parks.h"
#include <bits/stdc++.h>
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;
struct DSU{
    vector<int> bo,ss;
    void init(int x){
        bo.resize(x);
        ss.resize(x,1);
        iota(bo.begin(),bo.end(),0);
    }  
    int find(int x){
        return bo[x]==x?x:bo[x]=find(bo[x]);
    }
    int merge(int x,int y){
        x=find(x);
        y=find(y);
        if(x==y){
            return 0;
        }
        bo[x]=y;
        ss[y]+=ss[x];
        return 1;
    }
}dsu;

vector<int> au,av,aa,ab;
set<pair<int,int> > vis;
void ag(int a,int b,int c,int d){
    au.push_back(a);
    av.push_back(b);
    dsu.merge(a,b);
    aa.push_back(c);
    ab.push_back(d);
    vis.insert({c,d});
    //cout << a << " " << b << " " << c << " " << d << '\n';
}
int construct_roads(vector<int> x, vector<int> y) {
    vis.clear();
    if (x.size() == 1) {
	    build({}, {}, {}, {});
        return 1;
    }
    map<pair<int,int>,int> mp;
    int n=x.size();
    for(int i=0;i<n;i++){
        mp[{x[i],y[i]}]=i;
    }
    dsu.init(n);
    const int dx[4]={0,0,2,-2},dy[4]={2,-2,0,0};
    function<void(pair<int,int>,int)> dfs=[&](pair<int,int> w,int q){
        int a=0,b=0,c=0,d=0;
        if(dx[q]){
            a=b=dx[q]/2;
            c=1;
            d=-1;
        }
        else{
            a=1;
            b=-1;
            c=d=dy[q]/2;
        }
        int e=0,f=0,g=0,h=0;
        int way=2*(1-q/2);
        if(mp.find({w.fs+a,w.sc+c})==mp.end()){
            if(mp.find({w.fs+b,w.sc+d})==mp.end()){
                return;
            }
            way++;
        }
        if(dx[way]){
            e=f=dx[way]/2;
            g=1;
            h=-1;
        }
        else{
            e=1;
            f=-1;
            g=h=dy[way]/2;
        }
        for(int i=w.fs,j=w.sc;;i+=dx[way],j+=dy[way]){
            int sx=i+e,sy=j+g,tx=i+f,ty=j+h;
            if(mp.find({sx,sy})==mp.end() || mp.find({tx,ty})==mp.end()){
                if(way<2){
                    assert(mp.find({sx-dx[way],sy-dy[way]})!=mp.end());
                    assert(mp.find({tx-dx[way],ty-dy[way]})!=mp.end());
                    ag(mp[{sx-dx[way],sy-dy[way]}],mp[{tx-dx[way],ty-dy[way]}],i,j);
                }
                dfs({i,j},way);
                break;
            }
            else{
                if(vis.find({i+dx[way],j+dy[way]})!=vis.end()){
                    break;
                }
                if(way>=2){
                    ag(mp[{sx,sy}],mp[{tx,ty}],i+dx[way],j+dy[way]);
                }
            }
        }
    };
    for(int p=0;p<n;p++){
        int c=x[p]+2,d=y[p];
        if(mp.find({c,d})!=mp.end()){
            int a=mp[{c,d}];
            if(vis.find({x[p]+1,y[p]+1})==vis.end() && !(mp.find({x[p]+2,y[p]+2})!=mp.end() && mp.find({x[p],y[p]+2})!=mp.end())){
                ag(a,p,x[p]+1,y[p]+1);
                dfs({x[p]+1,y[p]+1},0);
            }
            else if(vis.find({x[p]+1,y[p]-1})==vis.end() && !(mp.find({x[p]+2,y[p]-2})!=mp.end() && mp.find({x[p],y[p]-2})!=mp.end())){
                ag(a,p,x[p]+1,y[p]-1);
                dfs({x[p]+1,y[p]-1},1);
            }
        }
    }
    for(int p=0;p<n;p++){
        int c=x[p]+2,d=y[p];
        if(mp.find({c,d})!=mp.end()){
            int a=mp[{c,d}];
            if(vis.find({x[p]+1,y[p]+1})==vis.end()){
                ag(a,p,x[p]+1,y[p]+1);
            }
            else if(vis.find({x[p]+1,y[p]-1})==vis.end()){
                ag(a,p,x[p]+1,y[p]-1);
            }
        }
    }
    for(int p=0;p<n;p++){
        int c=x[p],d=y[p]+2;
        if(mp.find({c,d})!=mp.end()){
            int a=mp[{c,d}];
            if(vis.find({x[p]+1,y[p]+1})==vis.end()){
                ag(a,p,x[p]+1,y[p]+1);
            }
            else if(vis.find({x[p]-1,y[p]+1})==vis.end()){
                ag(a,p,x[p]-1,y[p]+1);
            }
        }
    }
    if(dsu.ss[dsu.find(0)]!=n){
        return 0;
    }
    build(au,av,aa,ab);
    return 1;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 224 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 159 ms 18208 KB Output is correct
10 Correct 10 ms 2260 KB Output is correct
11 Correct 58 ms 10012 KB Output is correct
12 Correct 14 ms 3284 KB Output is correct
13 Correct 36 ms 6800 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 2 ms 468 KB Output is correct
16 Correct 151 ms 18216 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 224 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 159 ms 18208 KB Output is correct
10 Correct 10 ms 2260 KB Output is correct
11 Correct 58 ms 10012 KB Output is correct
12 Correct 14 ms 3284 KB Output is correct
13 Correct 36 ms 6800 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 2 ms 468 KB Output is correct
16 Correct 151 ms 18216 KB Output is correct
17 Incorrect 0 ms 212 KB Edge between 0 and 1 appears more than once: appeared on positions 0 and 2
18 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 224 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 159 ms 18208 KB Output is correct
10 Correct 10 ms 2260 KB Output is correct
11 Correct 58 ms 10012 KB Output is correct
12 Correct 14 ms 3284 KB Output is correct
13 Correct 36 ms 6800 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 2 ms 468 KB Output is correct
16 Correct 151 ms 18216 KB Output is correct
17 Incorrect 0 ms 212 KB Edge between 0 and 1 appears more than once: appeared on positions 0 and 2
18 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 224 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 159 ms 18208 KB Output is correct
10 Correct 10 ms 2260 KB Output is correct
11 Correct 58 ms 10012 KB Output is correct
12 Correct 14 ms 3284 KB Output is correct
13 Correct 36 ms 6800 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 2 ms 468 KB Output is correct
16 Correct 151 ms 18216 KB Output is correct
17 Incorrect 0 ms 212 KB Edge between 0 and 2 appears more than once: appeared on positions 0 and 2
18 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 224 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 159 ms 18208 KB Output is correct
10 Correct 10 ms 2260 KB Output is correct
11 Correct 58 ms 10012 KB Output is correct
12 Correct 14 ms 3284 KB Output is correct
13 Correct 36 ms 6800 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 2 ms 468 KB Output is correct
16 Correct 151 ms 18216 KB Output is correct
17 Incorrect 614 ms 46372 KB Edge between 168975 and 0 appears more than once: appeared on positions 0 and 100002
18 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 224 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 159 ms 18208 KB Output is correct
10 Correct 10 ms 2260 KB Output is correct
11 Correct 58 ms 10012 KB Output is correct
12 Correct 14 ms 3284 KB Output is correct
13 Correct 36 ms 6800 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 2 ms 468 KB Output is correct
16 Correct 151 ms 18216 KB Output is correct
17 Incorrect 0 ms 212 KB Edge between 0 and 1 appears more than once: appeared on positions 0 and 2
18 Halted 0 ms 0 KB -