oj.uz

Submission #896266

# Submission time Handle Problem Language Result Execution time Memory
896266 2024-01-01T06:54:14 Z abcvuitunggio Fountain Parks (IOI21_parks) C++17
5 / 100
 690 ms 189940 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 29272 KB Output is correct
2 Correct 7 ms 31324 KB Output is correct
3 Correct 7 ms 31324 KB Output is correct
4 Correct 6 ms 31324 KB Output is correct
5 Correct 7 ms 31324 KB Output is correct
6 Correct 6 ms 31324 KB Output is correct
7 Correct 6 ms 31324 KB Output is correct
8 Correct 7 ms 31324 KB Output is correct
9 Correct 386 ms 112348 KB Output is correct
10 Correct 24 ms 38940 KB Output is correct
11 Correct 123 ms 75036 KB Output is correct
12 Correct 35 ms 42744 KB Output is correct
13 Correct 81 ms 66520 KB Output is correct
14 Correct 8 ms 31944 KB Output is correct
15 Correct 10 ms 32588 KB Output is correct
16 Correct 368 ms 112384 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 29272 KB Output is correct
2 Correct 7 ms 31324 KB Output is correct
3 Correct 7 ms 31324 KB Output is correct
4 Correct 6 ms 31324 KB Output is correct
5 Correct 7 ms 31324 KB Output is correct
6 Correct 6 ms 31324 KB Output is correct
7 Correct 6 ms 31324 KB Output is correct
8 Correct 7 ms 31324 KB Output is correct
9 Correct 386 ms 112348 KB Output is correct
10 Correct 24 ms 38940 KB Output is correct
11 Correct 123 ms 75036 KB Output is correct
12 Correct 35 ms 42744 KB Output is correct
13 Correct 81 ms 66520 KB Output is correct
14 Correct 8 ms 31944 KB Output is correct
15 Correct 10 ms 32588 KB Output is correct
16 Correct 368 ms 112384 KB Output is correct
17 Incorrect 6 ms 31324 KB Tree @(3, 3) appears more than once: for edges on positions 0 and 1
18 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 29272 KB Output is correct
2 Correct 7 ms 31324 KB Output is correct
3 Correct 7 ms 31324 KB Output is correct
4 Correct 6 ms 31324 KB Output is correct
5 Correct 7 ms 31324 KB Output is correct
6 Correct 6 ms 31324 KB Output is correct
7 Correct 6 ms 31324 KB Output is correct
8 Correct 7 ms 31324 KB Output is correct
9 Correct 386 ms 112348 KB Output is correct
10 Correct 24 ms 38940 KB Output is correct
11 Correct 123 ms 75036 KB Output is correct
12 Correct 35 ms 42744 KB Output is correct
13 Correct 81 ms 66520 KB Output is correct
14 Correct 8 ms 31944 KB Output is correct
15 Correct 10 ms 32588 KB Output is correct
16 Correct 368 ms 112384 KB Output is correct
17 Incorrect 6 ms 31324 KB Tree @(3, 3) appears more than once: for edges on positions 0 and 1
18 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 29272 KB Output is correct
2 Correct 7 ms 31324 KB Output is correct
3 Correct 7 ms 31324 KB Output is correct
4 Correct 6 ms 31324 KB Output is correct
5 Correct 7 ms 31324 KB Output is correct
6 Correct 6 ms 31324 KB Output is correct
7 Correct 6 ms 31324 KB Output is correct
8 Correct 7 ms 31324 KB Output is correct
9 Correct 386 ms 112348 KB Output is correct
10 Correct 24 ms 38940 KB Output is correct
11 Correct 123 ms 75036 KB Output is correct
12 Correct 35 ms 42744 KB Output is correct
13 Correct 81 ms 66520 KB Output is correct
14 Correct 8 ms 31944 KB Output is correct
15 Correct 10 ms 32588 KB Output is correct
16 Correct 368 ms 112384 KB Output is correct
17 Correct 6 ms 31324 KB Output is correct
18 Incorrect 6 ms 31324 KB Tree @(199999, 199999) appears more than once: for edges on positions 0 and 1
19 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 29272 KB Output is correct
2 Correct 7 ms 31324 KB Output is correct
3 Correct 7 ms 31324 KB Output is correct
4 Correct 6 ms 31324 KB Output is correct
5 Correct 7 ms 31324 KB Output is correct
6 Correct 6 ms 31324 KB Output is correct
7 Correct 6 ms 31324 KB Output is correct
8 Correct 7 ms 31324 KB Output is correct
9 Correct 386 ms 112348 KB Output is correct
10 Correct 24 ms 38940 KB Output is correct
11 Correct 123 ms 75036 KB Output is correct
12 Correct 35 ms 42744 KB Output is correct
13 Correct 81 ms 66520 KB Output is correct
14 Correct 8 ms 31944 KB Output is correct
15 Correct 10 ms 32588 KB Output is correct
16 Correct 368 ms 112384 KB Output is correct
17 Incorrect 690 ms 189940 KB Tree @(100001, 100001) appears more than once: for edges on positions 130005 and 130006
18 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 29272 KB Output is correct
2 Correct 7 ms 31324 KB Output is correct
3 Correct 7 ms 31324 KB Output is correct
4 Correct 6 ms 31324 KB Output is correct
5 Correct 7 ms 31324 KB Output is correct
6 Correct 6 ms 31324 KB Output is correct
7 Correct 6 ms 31324 KB Output is correct
8 Correct 7 ms 31324 KB Output is correct
9 Correct 386 ms 112348 KB Output is correct
10 Correct 24 ms 38940 KB Output is correct
11 Correct 123 ms 75036 KB Output is correct
12 Correct 35 ms 42744 KB Output is correct
13 Correct 81 ms 66520 KB Output is correct
14 Correct 8 ms 31944 KB Output is correct
15 Correct 10 ms 32588 KB Output is correct
16 Correct 368 ms 112384 KB Output is correct
17 Incorrect 6 ms 31324 KB Tree @(3, 3) appears more than once: for edges on positions 0 and 1
18 Halted 0 ms 0 KB -