oj.uz

Submission #569617

# Submission time Handle Problem Language Result Execution time Memory
569617 2022-05-27T14:52:32 Z yoavL Land of the Rainbow Gold (APIO17_rainbow) C++14
11 / 100
 3000 ms 162572 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 });
        }
    }
    /*
    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 33 ms 340 KB Output is correct
2 Correct 172 ms 548 KB Output is correct
3 Correct 90 ms 340 KB Output is correct
4 Correct 102 ms 408 KB Output is correct
5 Correct 141 ms 580 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 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 120 ms 424 KB Output is correct
12 Correct 118 ms 448 KB Output is correct
13 Correct 330 ms 712 KB Output is correct
14 Correct 117 ms 596 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 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 1 ms 212 KB Output is correct
3 Execution timed out 3080 ms 74584 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 Correct 819 ms 90316 KB Output is correct
3 Correct 775 ms 90372 KB Output is correct
4 Correct 749 ms 84176 KB Output is correct
5 Correct 441 ms 48268 KB Output is correct
6 Correct 737 ms 119596 KB Output is correct
7 Incorrect 1090 ms 162572 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 340 KB Output is correct
2 Correct 172 ms 548 KB Output is correct
3 Correct 90 ms 340 KB Output is correct
4 Correct 102 ms 408 KB Output is correct
5 Correct 141 ms 580 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 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 120 ms 424 KB Output is correct
12 Correct 118 ms 448 KB Output is correct
13 Correct 330 ms 712 KB Output is correct
14 Correct 117 ms 596 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Execution timed out 3064 ms 20196 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 340 KB Output is correct
2 Correct 172 ms 548 KB Output is correct
3 Correct 90 ms 340 KB Output is correct
4 Correct 102 ms 408 KB Output is correct
5 Correct 141 ms 580 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 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 120 ms 424 KB Output is correct
12 Correct 118 ms 448 KB Output is correct
13 Correct 330 ms 712 KB Output is correct
14 Correct 117 ms 596 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Execution timed out 3064 ms 20196 KB Time limit exceeded
19 Halted 0 ms 0 KB -