Submission #1307381

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307381		opeleklanos	Fountain Parks (IOI21_parks)	C++20	15 / 100	72 ms	23592 KiB

parks

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include "parks.h"
using namespace std;


int xi[4] = {0, 0, +2, -2};
int yi[4] = {+2, -2, 0, 0};

int n;
vector<int> roadU;
vector<int> roadD;
vector<int> benchX;
vector<int> benchY;

#define X first.second 
#define Y first.first 

int construct_roads(vector<int> x, vector<int> y){
    n = x.size();
    vector<pair<pair<int, int>, int>> fount(n);
    
    for(int i = 0; i<n; i++){
        fount[i] = {{y[i], x[i]}, i};
    }
    sort(fount.begin(), fount.end());
    // reverse(fount.begin(), fount.end());

    vector<int> seen(n);
    stack<int> s;
    s.push(0);
    while(!s.empty()){
        int i = s.top();
        seen[i] = 1;
        s.pop();
        if(fount[i].X == fount[i+1].X && fount[i].Y + 2 == fount[i+1].Y&& !seen[i+1]){
            roadU.push_back(fount[i].second);
            roadD.push_back(fount[i+1].second);
            benchX.push_back((fount[i].X == 2)?1:5);
            benchY.push_back(fount[i].Y+1);
            if(!seen[i+1]) s.push(i+1);
        }
        if(fount[i].Y == fount[i-1].Y && fount[i].X - 2 == fount[i-1].X && !seen[i-1]){
            roadU.push_back(fount[i].second);
            roadD.push_back(fount[i-1].second);
            benchX.push_back(3);
            benchY.push_back(fount[i].Y+1);
            if(!seen[i-1]) s.push(i-1);
        }
        if(fount[i].X + 2 == fount[i+1].X && fount[i].Y == fount[i+1].Y&& !seen[i+1]){
            roadU.push_back(fount[i].second);
            roadD.push_back(fount[i+1].second);
            benchX.push_back(3);
            benchY.push_back(fount[i].Y+1);
            if(!seen[i+1]) s.push(i+1);
        }
        if(i<n-2 && fount[i].X == fount[i+2].X && fount[i].Y + 2 == fount[i+2].Y&& !seen[i+2]){
            roadU.push_back(fount[i].second);
            roadD.push_back(fount[i+2].second);
            benchX.push_back((fount[i].X == 2)?1:5);
            benchY.push_back(fount[i].Y+1);
            if(!seen[i+2]) s.push(i+2);
        }
    }
    
    for(int i = 0; i<n; i++) if(seen[i] == 0) return 0;
    build(roadU, roadD, benchX, benchY);

    return 1;
}

// int main(void){
//     freopen("input.txt", "r", stdin);
//     int ni;
//     cin>>ni;
//     vector<int> c1(ni), l1(ni);
//     for(int i = 0; i<ni; i++) cin>>c1[i];
//     for(int i = 0; i<ni; i++) cin>>l1[i];
    
//     int ans = construct_roads(c1, l1);
    
// }

// vector<vector<int>> grid;

// vector<vector<int>> vis;
// int found = 0;

// void dfs(int x, int y){
    //     vis[x][y] = 1;
    //     for(int i = 0; i<4; i++){
        //         if(grid[xi[i]+x][yi[i]+y] && !vis[xi[i]+x][yi[i]+y]){
            //             roadU.push_back(grid[x][y]-1);
            //             roadD.push_back(grid[xi[i]+x][yi[i]+y] - 1);
            //             if(x == 2 || y+xi[i] == 2)
            //         }
            //     }
            // }

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