oj.uz

Submission #569615

# Submission time Handle Problem Language Result Execution time Memory
569615 2022-05-27T14:49:55 Z yoavL Land of the Rainbow Gold (APIO17_rainbow) C++14
11 / 100
 3000 ms 550592 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 54 ms 440 KB Output is correct
2 Correct 338 ms 988 KB Output is correct
3 Correct 746 ms 1108 KB Output is correct
4 Correct 742 ms 1304 KB Output is correct
5 Correct 284 ms 1100 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 308 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 595 ms 1040 KB Output is correct
12 Correct 490 ms 1040 KB Output is correct
13 Correct 358 ms 1152 KB Output is correct
14 Correct 230 ms 1048 KB Output is correct
15 Correct 1 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 3095 ms 121340 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

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

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 440 KB Output is correct
2 Correct 338 ms 988 KB Output is correct
3 Correct 746 ms 1108 KB Output is correct
4 Correct 742 ms 1304 KB Output is correct
5 Correct 284 ms 1100 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 308 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 595 ms 1040 KB Output is correct
12 Correct 490 ms 1040 KB Output is correct
13 Correct 358 ms 1152 KB Output is correct
14 Correct 230 ms 1048 KB Output is correct
15 Correct 1 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 3095 ms 181644 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 440 KB Output is correct
2 Correct 338 ms 988 KB Output is correct
3 Correct 746 ms 1108 KB Output is correct
4 Correct 742 ms 1304 KB Output is correct
5 Correct 284 ms 1100 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 308 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 595 ms 1040 KB Output is correct
12 Correct 490 ms 1040 KB Output is correct
13 Correct 358 ms 1152 KB Output is correct
14 Correct 230 ms 1048 KB Output is correct
15 Correct 1 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 3095 ms 181644 KB Time limit exceeded
19 Halted 0 ms 0 KB -