oj.uz

Submission #569653

# Submission time Handle Problem Language Result Execution time Memory
569653 2022-05-27T15:17:43 Z yoavL Land of the Rainbow Gold (APIO17_rainbow) C++14
11 / 100
 3000 ms 163412 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 : adj) {
        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;
            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 254 ms 608 KB Output is correct
3 Correct 148 ms 432 KB Output is correct
4 Correct 160 ms 444 KB Output is correct
5 Correct 209 ms 628 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 216 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 185 ms 436 KB Output is correct
12 Correct 196 ms 476 KB Output is correct
13 Correct 356 ms 700 KB Output is correct
14 Correct 142 ms 624 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 1 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 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Execution timed out 3069 ms 74544 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 1605 ms 120856 KB Output is correct
3 Correct 1338 ms 120912 KB Output is correct
4 Correct 1113 ms 98204 KB Output is correct
5 Correct 893 ms 68012 KB Output is correct
6 Correct 785 ms 119960 KB Output is correct
7 Incorrect 1170 ms 163412 KB Output isn't correct
8 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 254 ms 608 KB Output is correct
3 Correct 148 ms 432 KB Output is correct
4 Correct 160 ms 444 KB Output is correct
5 Correct 209 ms 628 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 216 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 185 ms 436 KB Output is correct
12 Correct 196 ms 476 KB Output is correct
13 Correct 356 ms 700 KB Output is correct
14 Correct 142 ms 624 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Execution timed out 3046 ms 31116 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 254 ms 608 KB Output is correct
3 Correct 148 ms 432 KB Output is correct
4 Correct 160 ms 444 KB Output is correct
5 Correct 209 ms 628 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 216 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 185 ms 436 KB Output is correct
12 Correct 196 ms 476 KB Output is correct
13 Correct 356 ms 700 KB Output is correct
14 Correct 142 ms 624 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Execution timed out 3046 ms 31116 KB Time limit exceeded
19 Halted 0 ms 0 KB -