oj.uz

Submission #824724

# Submission time Handle Problem Language Result Execution time Memory
824724 2023-08-14T09:11:02 Z andrei_boaca Fountain Parks (IOI21_parks) C++17
5 / 100
 98 ms 25784 KB 
#include "parks.h"
#include <bits/stdc++.h>
//#include "grader.cpp"
using namespace std;

typedef pair<int,int> pii;
map<pii,int> ind;
struct point
{
    int x,y;
} v[200005];
int k;
vector<int> myy[200005];
vector<int> muchii[200005];
bool have[11][200005];
bool use[200005];
void dfs(int nod)
{
    use[nod]=1;
    for(int i:muchii[nod])
        if(!use[i])
            dfs(i);
}
int construct_roads(std::vector<int> X, std::vector<int> Y)
{
    k=X.size();
    int xmax=0;
    for(int i=0;i<k;i++)
    {
        v[i]={X[i],Y[i]};
        ind[{X[i],Y[i]}]=i;
        xmax=max(xmax,X[i]);
        myy[X[i]].push_back(Y[i]);
        have[X[i]][Y[i]]=1;
    }
    if(xmax<=2)
    {
        sort(myy[2].begin(),myy[2].end());
        vector<int> U,V,a,b;
        for(int i=1;i<myy[2].size();i++)
        {
            if(myy[2][i]-myy[2][i-1]!=2)
                return 0;
            int x=2;
            int yu=myy[2][i-1];
            int yv=myy[2][i];
            U.push_back(ind[{x,yu}]);
            V.push_back(ind[{x,yv}]);
            a.push_back(x-1);
            b.push_back(yv-1);
        }
        build(U,V,a,b);
        return 1;
    }
    if(xmax<=4)
    {
        sort(myy[2].begin(),myy[2].end());
        sort(myy[4].begin(),myy[4].end());
        vector<int> U,V,A,B;
        for(int i=2;i<=200000;i+=2)
            if(have[2][i]&&have[2][i-2])
            {
                int a=ind[{2,i}];
                int b=ind[{2,i-1}];
                U.push_back(a);
                V.push_back(b);
                muchii[a].push_back(b);
                muchii[b].push_back(a);
                A.push_back(1);
                B.push_back(i-1);
            }
        for(int i=2;i<=200000;i+=2)
            if(have[4][i]&&have[4][i-2])
            {
                int a=ind[{4,i}];
                int b=ind[{4,i-2}];
                U.push_back(a);
                V.push_back(b);
                muchii[a].push_back(b);
                muchii[b].push_back(a);
                A.push_back(5);
                B.push_back(i-1);
            }
        for(int i=2;i<=200000;i+=2)
            if(have[2][i]&&have[4][i])
            {
                int a=ind[{2,i}];
                int b=ind[{4,i}];
                U.push_back(a);
                V.push_back(b);
                muchii[a].push_back(b);
                muchii[b].push_back(a);
                A.push_back(3);
                B.push_back(i+1);
            }
        dfs(0);
        for(int i=0;i<k;i++)
            if(!use[i])
                return 0;
        build(U,V,A,B);
        return 1;
    }
}

Compilation message

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:40:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |         for(int i=1;i<myy[2].size();i++)
      |                     ~^~~~~~~~~~~~~~
parks.cpp:103:1: warning: control reaches end of non-void function [-Wreturn-type]
  103 | }
      | ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 4 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 4 ms 9684 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 4 ms 9684 KB Output is correct
9 Correct 98 ms 23880 KB Output is correct
10 Correct 11 ms 11348 KB Output is correct
11 Correct 43 ms 17392 KB Output is correct
12 Correct 14 ms 12088 KB Output is correct
13 Correct 22 ms 14468 KB Output is correct
14 Correct 5 ms 9812 KB Output is correct
15 Correct 6 ms 9812 KB Output is correct
16 Correct 93 ms 23908 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 4 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 4 ms 9684 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 4 ms 9684 KB Output is correct
9 Correct 98 ms 23880 KB Output is correct
10 Correct 11 ms 11348 KB Output is correct
11 Correct 43 ms 17392 KB Output is correct
12 Correct 14 ms 12088 KB Output is correct
13 Correct 22 ms 14468 KB Output is correct
14 Correct 5 ms 9812 KB Output is correct
15 Correct 6 ms 9812 KB Output is correct
16 Correct 93 ms 23908 KB Output is correct
17 Incorrect 6 ms 9684 KB Tree (a[0], b[0]) = (1, 3) is not adjacent to edge between u[0]=1 @(2, 4) and v[0]=0 @(4, 4)
18 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 4 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 4 ms 9684 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 4 ms 9684 KB Output is correct
9 Correct 98 ms 23880 KB Output is correct
10 Correct 11 ms 11348 KB Output is correct
11 Correct 43 ms 17392 KB Output is correct
12 Correct 14 ms 12088 KB Output is correct
13 Correct 22 ms 14468 KB Output is correct
14 Correct 5 ms 9812 KB Output is correct
15 Correct 6 ms 9812 KB Output is correct
16 Correct 93 ms 23908 KB Output is correct
17 Incorrect 6 ms 9684 KB Tree (a[0], b[0]) = (1, 3) is not adjacent to edge between u[0]=1 @(2, 4) and v[0]=0 @(4, 4)
18 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 4 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 4 ms 9684 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 4 ms 9684 KB Output is correct
9 Correct 98 ms 23880 KB Output is correct
10 Correct 11 ms 11348 KB Output is correct
11 Correct 43 ms 17392 KB Output is correct
12 Correct 14 ms 12088 KB Output is correct
13 Correct 22 ms 14468 KB Output is correct
14 Correct 5 ms 9812 KB Output is correct
15 Correct 6 ms 9812 KB Output is correct
16 Correct 93 ms 23908 KB Output is correct
17 Runtime error 11 ms 19416 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 4 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 4 ms 9684 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 4 ms 9684 KB Output is correct
9 Correct 98 ms 23880 KB Output is correct
10 Correct 11 ms 11348 KB Output is correct
11 Correct 43 ms 17392 KB Output is correct
12 Correct 14 ms 12088 KB Output is correct
13 Correct 22 ms 14468 KB Output is correct
14 Correct 5 ms 9812 KB Output is correct
15 Correct 6 ms 9812 KB Output is correct
16 Correct 93 ms 23908 KB Output is correct
17 Runtime error 44 ms 25784 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 4 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 4 ms 9684 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 4 ms 9684 KB Output is correct
9 Correct 98 ms 23880 KB Output is correct
10 Correct 11 ms 11348 KB Output is correct
11 Correct 43 ms 17392 KB Output is correct
12 Correct 14 ms 12088 KB Output is correct
13 Correct 22 ms 14468 KB Output is correct
14 Correct 5 ms 9812 KB Output is correct
15 Correct 6 ms 9812 KB Output is correct
16 Correct 93 ms 23908 KB Output is correct
17 Incorrect 6 ms 9684 KB Tree (a[0], b[0]) = (1, 3) is not adjacent to edge between u[0]=1 @(2, 4) and v[0]=0 @(4, 4)
18 Halted 0 ms 0 KB -