Submission #896266

#	Time	Username	Problem	Language	Result	Execution time	Memory
896266		abcvuitunggio	Fountain Parks (IOI21_parks)	C++17	5 / 100	690 ms	189940 KiB

parks

#include "parks.h"
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int INF=1e17;
struct Edge{
    int u,v,c;
    Edge(){};
    Edge (int u, int v, int c){
        this->u=u;
        this->v=v;
        this->c=c;
    }
};
struct Dinic{
    vector <Edge> s;
    vector <vector <int>> adj;
    vector <vector <int> :: iterator> cur;
    vector <int> h;
    int n, sink, source;
    void Reset(){
        s.clear();
        adj.clear();
        cur.clear();
        h.clear();
    }
    void Assign(int n){
        this->n=n;
        s.reserve(n+2);
        adj.resize(n+2);
        cur.resize(n+2);
        h.resize(n+2);
    }
    void AddEdge(int u, int v, int c){
        s.emplace_back(u,v,c);
        adj[u].emplace_back(s.size()-1);
        s.emplace_back(v,u,0);
        adj[v].emplace_back(s.size()-1);
    }
    bool bfs(){
        fill(h.begin(),h.end(),n+2);
        queue <int> q({sink});
        h[sink]=0;
        while (!q.empty()){
            int c=q.front();
            q.pop();
            for (int i:adj[c])
                if (h[s[i].v]==n+2&&s[i^1].c){
                    h[s[i].v]=h[c]+1;
                    if (s[i].v==source)
                        return true;
                    q.emplace(s[i].v);
                }
        }
        return false;
    }
    int dfs(int v, int flowin){
        if (v==sink)
            return flowin;
        int flowout=0;
        for (;cur[v]!=adj[v].end();++cur[v]){
            int i=*cur[v];
            if (!s[i].c||h[s[i].v]+1!=h[v])
                continue;
            int q=dfs(s[i].v,min(flowin,s[i].c));
            flowout+=q;
            if (flowin!=INF)
                flowin-=q;
            s[i].c-=q;
            s[i^1].c+=q;
            if (!flowin)
                break;
        }
        return flowout;
    }
    int BlockFlow(){
        for (int i=1;i<=n;i++)
            cur[i]=adj[i].begin();
        return dfs(source,INF);
    }
    int MaxFlow(int s, int t){
        source=s;
        sink=t;
        int res=0;
        while (bfs())
            res+=BlockFlow();
        return res;
    }
}g;
int n,dx[4]={1,-1,0,0},dy[4]={0,0,1,-1},p[200001],id;
pair <int, int> bench[400001];
map <int, int> mp[300001],mp2[300001];
int f(int i){
    return (p[i]==i?i:p[i]=f(p[i]));
}
bool unite(int i, int j){
    i=f(i);
    j=f(j);
    if (i==j)
        return false;
    p[j]=i;
    return true;
}
int32_t construct_roads(vector <int32_t> x, vector <int32_t> y) {
    if (x.size()==1){
        build({},{},{},{});
        return 1;
    }
    vector <int32_t> u,v,a,b;
    n=x.size();
    for (int i=0;i<n;i++)
        mp[x[i]][y[i]]=i;
    iota(p,p+n,0);
    g.Assign(n*3+10);
    for (int i=0;i<n;i++)
        for (int j=0;j<4;j++)
            if (mp[x[i]+dx[j]*2].count(y[i]+dy[j]*2)){
                int k=mp[x[i]+dx[j]*2][y[i]+dy[j]*2];
                if (unite(i,k)){
                    u.push_back(i);
                    v.push_back(k);
                    g.AddEdge(n*3+5,u.size(),1);
                    int X=x[i]+dx[j],Y=y[i]+dy[j];
                    for (int l=0;l<4;l++)
                        if (X+dx[l]!=x[i]&&Y+dy[l]!=y[i]){
                            if (!mp[X+dx[l]].count(Y+dy[l])){
                                mp[X+dx[l]][Y+dy[l]]=++id;
                                bench[id]={X+dx[l],Y+dy[l]};
                                g.AddEdge(id+n-1,n*3+6,1);
                            }
                            g.AddEdge(u.size(),mp[X+dx[l]][Y+dy[l]]+n-1,1);
                        }
                }
            }
    if (u.size()<n-1)
        return 0;
    a.assign(n-1,0);
    b.assign(n-1,0);
    int mx=g.MaxFlow(n*3+5,n*3+6);
    for (int i=0;i<g.s.size();i+=2)
        if (g.s[i].c&&g.s[i].u!=n*3+5&&g.s[i].v!=n*3+6){
            a[g.s[i].u-1]=bench[g.s[i].v-n+1].first;
            b[g.s[i].u-1]=bench[g.s[i].v-n+1].second;
        }
    build(u,v,a,b);
    return 1;
}

Compilation message (stderr)

parks.cpp: In function 'int32_t construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:135:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  135 |     if (u.size()<n-1)
      |         ~~~~~~~~^~~~
parks.cpp:140:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  140 |     for (int i=0;i<g.s.size();i+=2)
      |                  ~^~~~~~~~~~~
parks.cpp:139:9: warning: unused variable 'mx' [-Wunused-variable]
  139 |     int mx=g.MaxFlow(n*3+5,n*3+6);
      |         ^~

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