oj.uz

Submission #569649

# Submission time Handle Problem Language Result Execution time Memory
569649 2022-05-27T15:16:32 Z yoavL Land of the Rainbow Gold (APIO17_rainbow) C++14
11 / 100
 3000 ms 245092 KB 
#include "rainbow.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <queue>
#include <stack>
#include <bitset>
#include <math.h>
#include <fstream>
#include <iomanip>
#include <functional>
#include <numeric>
#include <chrono>
#include <random>

using namespace std;

using ll = int;
using ld = long double;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vvvvll = vector<vvvll>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vvvb = vector<vvb>;
using vld = vector<ld>;
using vvld = vector<vld>;
using vstr = vector<string>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;
using vvpll = vector<vpll>;
using pb = pair<bool, bool>;
using vpb = vector<pb>;
using vvpb = vector<vpb>;
using vi = vector<int>;
using vvi = vector<vi>;
using pi = pair<int, int>;
using vpi = vector<pi>;

const ll inf = (ll)2e18;
const ll mod = (ll)(1e9 + 7);

#define FAST        ios_base::sync_with_stdio(0)
#define FASTIN		cin.tie(0)
#define FASTOUT		cout.tie(0)

#define upmin(a, b) (a) = min((a), (b))
#define upmax(a, b) (a) = max((a), (b))

#define pr(x) cout << x << endl
#define prv(v) for(auto it : v) cout << it << " "; cout << endl;
#define prvv(v) for(auto it : v) { for(auto it2 : it) cout << it2 << " "; cout << endl; } cout << endl;
#define spr(x) cout << x << " "

#define DBG_FLAG (1) // Toggle to switch between bebug mode and solution mode
#ifdef DBG_FLAG
#define wpr(x) cout << #x << ": " << (x) << endl;
#define wprv(v) cout << #v << ": " << endl; for(auto it : v) cout << it << " "; cout << endl;
#define wprvv(v) cout << #v << ": " << endl; for(auto it : v) { for(auto it2 : it) cout << it2 << " "; cout << endl; } cout << endl;
#define wspr(x) cout << #x << ": " << x << " "
#endif

#ifndef DBG_FLAG
#define wpr(x)
#define wprv(v)
#define wprvv(v)
#define wspr(x)
#endif

#define rep(i, s, e) for(ll i = s; i < e; i++)
#define all(x) (x).begin(), (x).end()

#define x first
#define y second

/*

Solution:

Walk through all of the nodes adjecent to the river.
That is good enough. Complexity:
O(q * min(M, r*c)) = O(q * M)

Should solve:

Subtask 1, Subtask 3.

Total points: 35

*/

vpll adj;
vpll path;
set<pll> isPath, isAdj;
ll r, c, m, sr, sc;
ll xdir[] = { -1, 1, 0, 0 };
ll ydir[] = { 0, 0, -1, 1 };
ll extxdir[] = { -1, 1, 0, 0, 1, 1, -1, -1 };
ll extydir[] = { 0, 0, -1, 1, 1, -1, 1, -1};


ostream& operator<<(ostream & os, const pll & p)
{
    cout << "{" << p.x << ", " << p.y << "}";
    return os;
}

void init(int R, int C, int Sr, int Sc, int M, char* S)
{
    r = R, c = C, sr = Sr - 1, sc = Sc - 1, m = M + 1;
    
    path.resize(m);
    path[0] = { sr, sc };
    rep(i, 0, m - 1) {
        ll x = path[i].x, y = path[i].y;
        if (S[i] == 'N') x--;
        if (S[i] == 'S') x++;
        if (S[i] == 'W') y--;
        if (S[i] == 'E') y++;
        path[i + 1] = { x, y };
    }
    rep(i, 0, m) {
        ll x = path[i].x, y = path[i].y;
        isPath.insert({ x, y });
    }
    rep(i, 0, m) {
        ll x = path[i].x, y = path[i].y;
        rep(dir, 0, 8) {
            ll nx = x + extxdir[dir];
            ll ny = y + extydir[dir];
            if (nx < 0 || nx >= r || ny < 0 || ny >= c) continue;
            if (isPath.find({ nx, ny }) != isPath.end()) continue;
            adj.push_back({ nx, ny });
            isAdj.insert({ nx, ny });
        }
    }
    for(const auto& loc : isAdj) {
        ll x = loc.x, y = loc.y;
        rep(dir, 0, 4) {
            ll nx = x + xdir[dir];
            ll ny = y + ydir[dir];
            if (nx < 0 || nx >= r || ny < 0 || ny >= c) continue;
            if (isPath.find({ nx, ny }) != isPath.end()) continue;
            adj.push_back({ nx, ny });
            isAdj.insert({ nx, ny });
        }
    }
    /*
    rep(i, 0, r) {
        rep(j, 0, c) {
            isAdj.insert({ i, j });
        }
    }
    */
    sort(path.begin(), path.end());
    path.erase(unique(path.begin(), path.end()), path.end());
    sort(adj.begin(), adj.end());
    adj.erase(unique(adj.begin(), adj.end()), adj.end());
    
    //wprv(path);
}


void dfs_rect(ll x, ll y, ll ar, ll ac, ll br, ll bc, set<pll>& vis, set<pll>& check)
{
    vis.insert({ x, y });
    rep(dir, 0, 4) {
        ll nx = x + xdir[dir];
        ll ny = y + ydir[dir];
        if (nx < ar || nx > br || ny < ac || ny > bc) continue;
        if (isPath.find({ nx, ny }) != isPath.end()) continue;
        if (check.find({ nx, ny }) == check.end()) continue;
        if (vis.find({ nx, ny }) != vis.end()) continue;
        dfs_rect(nx, ny, ar, ac, br, bc, vis, check);
    }
}

int colour(int ar, int ac, int br, int bc) {
    ar--, ac--;
    br--, bc--;
    ll components = 0;
    set<pll> check = isAdj;
    rep(j, ac, bc + 1) {
        check.insert({ ar, j });
        check.insert({ br, j });
    }
    rep(i, ar, br + 1) {
        check.insert({ i, ac });
        check.insert({ i, bc });
    }
    //wprv(check);
    set<pll> vis;
    for (const auto& loc : check) {
        ll nx = loc.x, ny = loc.y;
        if (nx < ar || nx > br || ny < ac || ny > bc) continue;
        if (vis.find({ nx, ny }) != vis.end()) continue;
        if (isPath.find({ nx, ny }) != isPath.end()) continue;
        components++;
        dfs_rect(nx, ny, ar, ac, br, bc, vis, check);
    }
    
    return components;
}

/*


6 4 9 4 
3 3 
NWESSWEWS 
2 3 2 3 
3 2 4 4 
5 3 6 4 
1 2 5 3 


*/

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 372 KB Output is correct
2 Correct 264 ms 676 KB Output is correct
3 Correct 708 ms 1008 KB Output is correct
4 Correct 718 ms 972 KB Output is correct
5 Correct 214 ms 724 KB Output is correct
6 Correct 0 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 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 484 ms 916 KB Output is correct
12 Correct 216 ms 508 KB Output is correct
13 Correct 265 ms 700 KB Output is correct
14 Correct 131 ms 620 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Execution timed out 3076 ms 95656 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Execution timed out 3075 ms 245092 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 372 KB Output is correct
2 Correct 264 ms 676 KB Output is correct
3 Correct 708 ms 1008 KB Output is correct
4 Correct 718 ms 972 KB Output is correct
5 Correct 214 ms 724 KB Output is correct
6 Correct 0 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 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 484 ms 916 KB Output is correct
12 Correct 216 ms 508 KB Output is correct
13 Correct 265 ms 700 KB Output is correct
14 Correct 131 ms 620 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Execution timed out 3082 ms 158616 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 372 KB Output is correct
2 Correct 264 ms 676 KB Output is correct
3 Correct 708 ms 1008 KB Output is correct
4 Correct 718 ms 972 KB Output is correct
5 Correct 214 ms 724 KB Output is correct
6 Correct 0 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 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 484 ms 916 KB Output is correct
12 Correct 216 ms 508 KB Output is correct
13 Correct 265 ms 700 KB Output is correct
14 Correct 131 ms 620 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Execution timed out 3082 ms 158616 KB Time limit exceeded
19 Halted 0 ms 0 KB -