QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#33791 | #4231. Rafting Trip | BalintR# | WA | 24ms | 29348kb | C++ | 3.8kb | 2022-06-05 08:23:58 | 2022-06-05 08:23:58 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef unsigned uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<pii> vpii;
typedef complex<double> cmplx;
template <typename T> using minPq = priority_queue<T, vector<T>, greater<T>>;
#define boost() cin.sync_with_stdio(0); cin.tie(0)
#define ms(a, x) memset(a, x, sizeof(a))
#define pb push_back
#define fs first
#define sn second
#define ALL(v) (v).begin(), (v).end()
#define SZ(v) ((int) (v).size())
#define lbv(v, x) (lower_bound((v).begin(), (v).end(), x) - (v).begin())
#define ubv(v, x) (upper_bound((v).begin(), (v).end(), x) - (v).begin())
template <typename T> inline void UNIQUE(vector<T> &v){sort(ALL(v)); v.resize(unique(ALL(v)) - v.begin());}
const int INF = 0x3f3f3f3f;
const ll LLINF = 0x3f3f3f3f3f3f3f3f;
const double PI = acos(-1);
#define FR(i, n) for(int i = 0; i < (n); i++)
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define FORR(i, a, b) for(int i = (a); i >= (b); i--)
#define dbg(x) {cerr << #x << ' ' << x << endl;}
#define dbgArr(arr, n) {cerr << #arr; FR(_i, n) cerr << ' ' << arr[_i]; cerr << endl;}
const pii MOVES[4] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
const int MW = 512;
const int MN = MW*MW;
int n, h, w;
string grid[MW];
int getCell(int i, int j){
if(i < 0 || i >= h || j < 0 || j >= w || grid[i][j] == '.' || grid[i][j] == '#') return -1;
return i*w + j;
}
bool exist[MN], vis[MN];
int nxt[MN];
vi adjList[MN];
vi vals[MN];
int freq[MN];
int cur;
int ans;
int st[MN], si;
void checkLoop(int n1){
if(vis[n1]) return;
si = 0;
while(!vis[n1]){
st[si++] = n1;
vis[n1] = true;
n1 = nxt[n1];
if(n1 == -1) return;
}
int start = -1;
FR(i, si){
if(st[i] == n1){
start = i;
break;
}
}
if(start == -1) return;
set<int> loop;
FOR(i, start, si) loop.insert(st[i]);
FOR(i, start+1, si){
int n2 = st[i];
exist[n2] = false;
nxt[n2] = -3;
for(int n3 : adjList[n2]) adjList[n1].pb(n3);
for(int a : vals[n2]) vals[n1].pb(a);
}
nxt[n1] = -1;
UNIQUE(adjList[n1]);
UNIQUE(vals[n1]);
vi newAl;
for(int n2 : adjList[n1]) if(loop.find(n2) == loop.end()) newAl.pb(n2);
adjList[n1] = newAl;
/*cerr << "loop";
FOR(i, start, si) cerr << ' ' << st[i];
cerr << endl;*/
}
void dfs(int n1){
for(int a : vals[n1]) cur += !(freq[a]++);
ans = max(ans, cur);
for(int n2 : adjList[n1]) dfs(n2);
for(int a : vals[n1]) cur -= !(--freq[a]);
}
int main(){
boost();
cin >> h >> w;
n = h*w;
fill(nxt, nxt + n, -2);
FR(i, h){
cin >> grid[i];
FR(j, w){
exist[i*w + j] = grid[i][j] != '.' && grid[i][j] != '#';
if(grid[i][j] == '>') nxt[getCell(i, j)] = getCell(i, j+1);
if(grid[i][j] == '<') nxt[getCell(i, j)] = getCell(i, j-1);
if(grid[i][j] == '^') nxt[getCell(i, j)] = getCell(i-1, j);
if(grid[i][j] == 'v') nxt[getCell(i, j)] = getCell(i+1, j);
if(grid[i][j] == '#'){
for(auto [dx, dy] : MOVES){
int x = i+dx, y = j+dy;
int c = getCell(x, y);
if(c == -1) continue;
vals[c].pb(i*w + j);
}
}
}
}
FR(i, n){
if(exist[i] && nxt[i] != -1) adjList[nxt[i]].pb(i);
}
/*dbgArr(exist, n);
dbgArr(nxt, n);
FR(i, n) dbgArr(vals[i].begin(), SZ(vals[i]));*/
FR(i, n) checkLoop(i);
//FR(i, n) dbgArr(adjList[i].begin(), SZ(adjList[i]));
FR(i, n) if(nxt[i] == -1) dfs(i);
cout << ans << '\n';
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 17872kb
input:
5 6 v<<<#v v#v<.> >>v<<< ..v##^ #<<<.^
output:
4
result:
ok single line: '4'
Test #2:
score: 0
Accepted
time: 0ms
memory: 16212kb
input:
4 5 >v<<. ^<..# #...# .#>^#
output:
2
result:
ok single line: '2'
Test #3:
score: 0
Accepted
time: 2ms
memory: 17932kb
input:
4 6 >>v#>v ^#>>^v ^<<#v< .#^<<#
output:
5
result:
ok single line: '5'
Test #4:
score: 0
Accepted
time: 5ms
memory: 18004kb
input:
6 6 ^.>>>> ^..... ^....v ^....v #....v <<<<#v
output:
2
result:
ok single line: '2'
Test #5:
score: 0
Accepted
time: 2ms
memory: 16020kb
input:
6 7 ^>>>>>v ^.....v ^.#^..v ^.#^<.v ^.....v ^<<<<<<
output:
2
result:
ok single line: '2'
Test #6:
score: 0
Accepted
time: 2ms
memory: 18056kb
input:
3 7 >v<<<<# ^<##### #^<<<<<
output:
6
result:
ok single line: '6'
Test #7:
score: 0
Accepted
time: 2ms
memory: 17928kb
input:
3 5 ><.v# ##.^# ...#.
output:
3
result:
ok single line: '3'
Test #8:
score: 0
Accepted
time: 2ms
memory: 18012kb
input:
7 3 ### #># ### ... ### #>. ###
output:
4
result:
ok single line: '4'
Test #9:
score: 0
Accepted
time: 6ms
memory: 16268kb
input:
2 2 >. .#
output:
0
result:
ok single line: '0'
Test #10:
score: 0
Accepted
time: 5ms
memory: 17868kb
input:
2 2 .. .v
output:
0
result:
ok single line: '0'
Test #11:
score: -100
Wrong Answer
time: 24ms
memory: 29348kb
input:
498 498 <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<...
output:
23336
result:
wrong answer 1st lines differ - expected: '41195', found: '23336'