Submission #803219

#	Time	Username	Problem	Language	Result	Execution time	Memory
803219		vjudge1	Fountain Parks (IOI21_parks)	C++17	5 / 100	39 ms	7484 KiB

parks

#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 (stderr)

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 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30