oj.uz

Submission #803219

# Submission time Handle Problem Language Result Execution time Memory
803219 2023-08-03T01:26:51 Z vjudge1 Fountain Parks (IOI21_parks) C++17
5 / 100
 39 ms 7484 KB 
#include "parks.h"
#include<bits/stdc++.h>
using namespace std;
bitset<200100> have[7];
int at[7][200100];
int construct1(int row) {
    vector<int>u,v,x,y;
    int prev = 0;
    for(int i = 2; i <= 200000; i+=2) {
        if(have[row][i]) {
            if(prev) {
                if(i-prev>2)
                    return 0;
                u.push_back(at[row][i]);
                v.push_back(at[row][i-2]);
                x.push_back(row+1);
                y.push_back(i-1);
            }
            prev = i;
        }
    }
    build(u,v,x,y);
    return 1;
}
int construct2(int row1, int row2) {
    int prev1 = 0, prev2 = 0, co1=1, co2=1;
    vector<pair<pair<int, int>, pair<int, int>>> edges;
    for(int i = 2; i <= 200000; i+=2) {
        if(have[row2][i]&&i>2){
            if(have[row2][i-2])
                edges.push_back({{at[row2][i], at[row2][i-2]}, {row2+1, i-1}});
            else co2 = 0;
        }
        if(have[row1][i]) {
            if(i>2) {
                if(have[row1][i-2])
                    edges.push_back({{at[row1][i], at[row1][i-2]}, {row1-1, i-1}});
                else co1 = 0;
            }
            if(have[row2][i])
                edges.push_back({{at[row1][i], at[row2][i]}, {row1+1, i-1}}),co1|=co2,co2=co1;
        }
    }
    if(!co1||!co2) return 0;
    vector<int> u,v,x,y;
    for(auto i: edges)
        u.push_back(i.first.first), v.push_back(i.first.second),x.push_back(i.second.first),y.push_back(i.second.second);
    build(u,v,x,y);
    return 1;
}
int construct_roads(vector<int> x, vector<int> y) {
    int n = x.size();
    for(int i = 0; i < n; i++)
        have[x[i]][y[i]] = 1,at[x[i]][y[i]]=i;
    int a = have[2].count(), b = have[4].count(), c = have[6].count();
    if(a&&c&&!b) return 0;
    if(!a&&!b) return construct1(6);
    if(!a&&!c) return construct1(4);
    if(!c&&!b) return construct1(2);
    if(!b) return construct2(2,6);
    if(!c) return construct2(2,4);
    if(!a) return construct2(4,6);
    return 1;
}

Compilation message

parks.cpp: In function 'int construct2(int, int)':
parks.cpp:26:9: warning: unused variable 'prev1' [-Wunused-variable]
   26 |     int prev1 = 0, prev2 = 0, co1=1, co2=1;
      |         ^~~~~
parks.cpp:26:20: warning: unused variable 'prev2' [-Wunused-variable]
   26 |     int prev1 = 0, prev2 = 0, co1=1, co2=1;
      |                    ^~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 39 ms 7476 KB Output is correct
10 Correct 4 ms 1252 KB Output is correct
11 Correct 25 ms 4188 KB Output is correct
12 Correct 8 ms 1620 KB Output is correct
13 Correct 7 ms 2072 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 39 ms 7484 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 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 39 ms 7476 KB Output is correct
10 Correct 4 ms 1252 KB Output is correct
11 Correct 25 ms 4188 KB Output is correct
12 Correct 8 ms 1620 KB Output is correct
13 Correct 7 ms 2072 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 39 ms 7484 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Incorrect 1 ms 292 KB Solution announced impossible, but it is possible.
19 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 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 39 ms 7476 KB Output is correct
10 Correct 4 ms 1252 KB Output is correct
11 Correct 25 ms 4188 KB Output is correct
12 Correct 8 ms 1620 KB Output is correct
13 Correct 7 ms 2072 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 39 ms 7484 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Incorrect 1 ms 292 KB Solution announced impossible, but it is possible.
19 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 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 39 ms 7476 KB Output is correct
10 Correct 4 ms 1252 KB Output is correct
11 Correct 25 ms 4188 KB Output is correct
12 Correct 8 ms 1620 KB Output is correct
13 Correct 7 ms 2072 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 39 ms 7484 KB Output is correct
17 Runtime error 1 ms 340 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 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 39 ms 7476 KB Output is correct
10 Correct 4 ms 1252 KB Output is correct
11 Correct 25 ms 4188 KB Output is correct
12 Correct 8 ms 1620 KB Output is correct
13 Correct 7 ms 2072 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 39 ms 7484 KB Output is correct
17 Runtime error 30 ms 6740 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 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 39 ms 7476 KB Output is correct
10 Correct 4 ms 1252 KB Output is correct
11 Correct 25 ms 4188 KB Output is correct
12 Correct 8 ms 1620 KB Output is correct
13 Correct 7 ms 2072 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 39 ms 7484 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Incorrect 1 ms 292 KB Solution announced impossible, but it is possible.
19 Halted 0 ms 0 KB -