oj.uz

Submission #569616

# Submission time Handle Problem Language Result Execution time Memory
569616 2022-05-27T14:50:40 Z yoavL Land of the Rainbow Gold (APIO17_rainbow) C++14
11 / 100
 3000 ms 207396 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 = long long;
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 31 ms 384 KB Output is correct
2 Correct 162 ms 788 KB Output is correct
3 Correct 84 ms 340 KB Output is correct
4 Correct 105 ms 448 KB Output is correct
5 Correct 151 ms 724 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 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 118 ms 476 KB Output is correct
12 Correct 124 ms 588 KB Output is correct
13 Correct 300 ms 868 KB Output is correct
14 Correct 119 ms 852 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 3070 ms 96348 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 934 ms 120844 KB Output is correct
3 Correct 845 ms 121036 KB Output is correct
4 Correct 818 ms 111572 KB Output is correct
5 Correct 472 ms 66328 KB Output is correct
6 Correct 868 ms 152640 KB Output is correct
7 Incorrect 1206 ms 207396 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 384 KB Output is correct
2 Correct 162 ms 788 KB Output is correct
3 Correct 84 ms 340 KB Output is correct
4 Correct 105 ms 448 KB Output is correct
5 Correct 151 ms 724 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 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 118 ms 476 KB Output is correct
12 Correct 124 ms 588 KB Output is correct
13 Correct 300 ms 868 KB Output is correct
14 Correct 119 ms 852 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 3091 ms 30212 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 384 KB Output is correct
2 Correct 162 ms 788 KB Output is correct
3 Correct 84 ms 340 KB Output is correct
4 Correct 105 ms 448 KB Output is correct
5 Correct 151 ms 724 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 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 118 ms 476 KB Output is correct
12 Correct 124 ms 588 KB Output is correct
13 Correct 300 ms 868 KB Output is correct
14 Correct 119 ms 852 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 3091 ms 30212 KB Time limit exceeded
19 Halted 0 ms 0 KB -