oj.uz

Submission #907447

# Submission time Handle Problem Language Result Execution time Memory
907447 2024-01-15T15:32:49 Z arnavai Tracks in the Snow (BOI13_tracks) C++14
45.3125 / 100
 2000 ms 1048576 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
#define all(x) (x).begin(), (x).end()
#define inf 1000000007
#define llmax LLONG_MAX
#define pi 3.141592653589793238462643383279502884197169399
 
long long binpow(long long a, long long b) {
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}
ll ncr(int n, int r)
{
    if (n < r) return 0;
    long long p = 1, k = 1;
    if (n - r < r)
        r = n - r;
    if (r != 0) {
        while (r) {
            p *= n;
            k *= r;
            long long m = __gcd(p, k);
            p /= m;
            k /= m;
            n--;
            r--;
        }
    }
    else
        p = 1;
    return p;
}

vector <ll> vcreate(int n){
    vector <ll> v(n);
    for (int i = 0; i < n; i++)
    {
        cin>>v[i];
    }
    return v;
}

void dfs(vector<vector<char>>&v, char z, int x, int y)
{
    char find;
    if(z=='R') 
    {
        v[x][y]='F';
        find='R';
    }
    else
    {
        v[x][y]='R';
        find = 'F';
    }
    int h = v.size();
    int w = v[0].size();
    int dx[] = {-1, 1, 0, 0};
    int dy[] = {0,0,-1,1};
    for(int i = 0; i<4; i++)
    {
        if(x+dx[i]>=0 and x+dx[i]<h and y+dy[i]>=0 and y+dy[i]<w and v[x+dx[i]][y+dy[i]]==find)
        {
            dfs(v, z, x+dx[i], y+dy[i]);
        }
    }
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout); 

    int h, w; cin>>h>>w;
    vector<vector<char>>v(h, vector<char>(w));
    for(int i = 0; i<h; i++)
    {
        for(int j = 0; j<w; j++)
        {
            cin>>v[i][j];
        }
    }
    int ans = 1;
    while(true)
    {
        char z = v[0][0];
        dfs(v, z, 0, 0);
        ans++;
        set<char> s;
        for(int i =0; i<h; i++)
        {
            for(int j = 0; j<w; j++)
            {
                if(v[i][j]!='.') s.insert(v[i][j]);
            }
        }
        if(s.size()==1) break;
        
    }
    cout<<ans<<'\n';

}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 381 ms 31648 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 2 ms 344 KB Output is correct
4 Correct 33 ms 24144 KB Output is correct
5 Correct 64 ms 2132 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 2 ms 348 KB Output is correct
8 Correct 1 ms 1136 KB Output is correct
9 Correct 3 ms 348 KB Output is correct
10 Correct 58 ms 1620 KB Output is correct
11 Correct 6 ms 6488 KB Output is correct
12 Correct 59 ms 10412 KB Output is correct
13 Correct 67 ms 1868 KB Output is correct
14 Correct 65 ms 1760 KB Output is correct
15 Correct 338 ms 6368 KB Output is correct
16 Correct 386 ms 31404 KB Output is correct
17 Correct 382 ms 8528 KB Output is correct
18 Correct 31 ms 24148 KB Output is correct

Subtask #2
15.3125 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1606 ms 2908 KB Output is correct
2 Execution timed out 2009 ms 19888 KB Time limit exceeded
3 Execution timed out 2029 ms 33200 KB Time limit exceeded
4 Execution timed out 2021 ms 20352 KB Time limit exceeded
5 Execution timed out 2025 ms 19028 KB Time limit exceeded
6 Execution timed out 2111 ms 1026592 KB Time limit exceeded
7 Correct 1227 ms 2128 KB Output is correct
8 Correct 1563 ms 2960 KB Output is correct
9 Correct 126 ms 2976 KB Output is correct
10 Correct 333 ms 1324 KB Output is correct
11 Correct 358 ms 1312 KB Output is correct
12 Correct 1509 ms 2060 KB Output is correct
13 Execution timed out 2012 ms 19900 KB Time limit exceeded
14 Execution timed out 2061 ms 15240 KB Time limit exceeded
15 Execution timed out 2028 ms 2648 KB Time limit exceeded
16 Execution timed out 2053 ms 11092 KB Time limit exceeded
17 Execution timed out 2061 ms 16252 KB Time limit exceeded
18 Execution timed out 2012 ms 8908 KB Time limit exceeded
19 Execution timed out 2037 ms 21244 KB Time limit exceeded
20 Execution timed out 2086 ms 7760 KB Time limit exceeded
21 Execution timed out 2019 ms 19536 KB Time limit exceeded
22 Execution timed out 2031 ms 19048 KB Time limit exceeded
23 Execution timed out 2092 ms 20456 KB Time limit exceeded
24 Execution timed out 2021 ms 19024 KB Time limit exceeded
25 Execution timed out 2008 ms 33108 KB Time limit exceeded
26 Runtime error 836 ms 1048576 KB Execution killed with signal 9
27 Runtime error 1525 ms 1048576 KB Execution killed with signal 9
28 Execution timed out 2115 ms 1042004 KB Time limit exceeded
29 Execution timed out 2174 ms 1048576 KB Time limit exceeded
30 Runtime error 1706 ms 1048576 KB Execution killed with signal 9
31 Execution timed out 2057 ms 143164 KB Time limit exceeded
32 Runtime error 1130 ms 1048576 KB Execution killed with signal 9