oj.uz

Submission #1093067

# Submission time Handle Problem Language Result Execution time Memory
1093067 2024-09-25T19:08:31 Z mm77 Tracks in the Snow (BOI13_tracks) C++14
0 / 100
 1377 ms 1048576 KB 
#include<bits/stdc++.h>
using namespace std;
const int N=4e3+4;
pair<int,int>anc[N][N];
char t[N][N];
vector<pair<int,int>>f[N][N];
vector<pair<int,int>>r[N][N];
pair<int,int>fF(int x,int y)
{
    if(anc[x][y].first==x&&anc[x][y].second==y)return {x,y};
    return anc[x][y]=fF(anc[x][y].first,anc[x][y].second);
}
void uF(int x,int y,int a,int b)
{
    if(fF(x,y)==fF(a,b))return;
    pair<int,int>p=fF(x,y);
    pair<int,int>p2=fF(a,b);

    x=p.first,y=p.second;
    a=p2.first,b=p2.second;
    if(f[x][y].size()>f[a][b].size())
    {
        swap(x,a);
        swap(y,b);
    }
    anc[x][y]={a,b};
    for(auto p:f[x][y])
    {
        f[a][b].push_back(p);
    }
    f[x][y].clear();
}
void uR(int x,int y,int a,int b)
{
    if(fF(x,y)==fF(a,b))return ;
    pair<int,int>p=fF(x,y);
    pair<int,int>p2=fF(a,b);
    x=p.first,y=p.second;
    a=p2.first,b=p2.second;
    if(r[x][y].size()>r[a][b].size())
    {
        swap(x,a);
        swap(y,b);
    }
    anc[x][y]={a,b};
    for(auto p:r[x][y])
    {
        r[a][b].push_back(p);
    }
    r[x][y].clear();
}
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {
            cin>>t[i][j];
            anc[i][j]={i,j};
            if(t[i][j]=='R')r[i][j].push_back({i,j});
            if(t[i][j]=='F')f[i][j].push_back({i,j});
        }
    }
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {
            if(t[i][j]=='R'&&t[i-1][j]=='R')uR(i,j,i-1,j);
            if(t[i][j]=='R'&&t[i][j-1]=='R')uR(i,j,i,j-1);
        }
    }
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {
            if(t[i][j]=='F'&&t[i-1][j]=='F')uF(i,j,i-1,j);
            if(t[i][j]=='F'&&t[i][j-1]=='F')uF(i,j,i,j-1);
        }
    }
    char akt=t[1][1];
    int res=0;
    while(true)
    {
        if(akt=='F'&&f[anc[1][1].first][anc[1][1].second].size()==0)break;
        if(akt=='R'&&r[anc[1][1].first][anc[1][1].second].size()==0)break;
        res++;
        if(akt=='R')
        {
            for(auto p:r[anc[1][1].first][anc[1][1].second])
            {
                int i=p.first,j=p.second;
                if(t[i-1][j]=='F')uF(i,j,i-1,j);
                if(t[i][j-1]=='F')uF(i,j,i,j-1);
                if(t[i+1][j]=='F')uF(i,j,i+1,j);
                if(t[i][j+1]=='F')uF(i,j,i,j+1);
            }
            r[anc[1][1].first][anc[1][1].second].clear();
        }
        else
        {
            for(auto p:f[anc[1][1].first][anc[1][1].second])
            {
                int i=p.first,j=p.second;
                if(t[i-1][j]=='R')uR(i,j,i-1,j);
                if(t[i][j-1]=='R')uR(i,j,i,j-1);
                if(t[i+1][j]=='R')uR(i,j,i+1,j);
                if(t[i][j+1]=='R')uR(i,j,i,j+1);
            }
            f[anc[1][1].first][anc[1][1].second].clear();
        }
        if(akt=='R')akt='F';
        else akt='R';
    }
    cout<<res<<"\n";
    return 0;
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 370 ms 769872 KB Output isn't correct
2 Incorrect 310 ms 753488 KB Output isn't correct
3 Incorrect 317 ms 753748 KB Output isn't correct
4 Incorrect 343 ms 765448 KB Output isn't correct
5 Incorrect 308 ms 757020 KB Output isn't correct
6 Incorrect 330 ms 753488 KB Output isn't correct
7 Incorrect 297 ms 753748 KB Output isn't correct
8 Incorrect 301 ms 753968 KB Output isn't correct
9 Incorrect 300 ms 754312 KB Output isn't correct
10 Incorrect 316 ms 756888 KB Output isn't correct
11 Incorrect 314 ms 757244 KB Output isn't correct
12 Incorrect 341 ms 760148 KB Output isn't correct
13 Incorrect 313 ms 757188 KB Output isn't correct
14 Incorrect 316 ms 757084 KB Output isn't correct
15 Incorrect 366 ms 767312 KB Output isn't correct
16 Incorrect 354 ms 769872 KB Output isn't correct
17 Incorrect 327 ms 763728 KB Output isn't correct
18 Incorrect 322 ms 765448 KB Output isn't correct

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 317 ms 784596 KB Output isn't correct
2 Incorrect 476 ms 804192 KB Output isn't correct
3 Incorrect 1377 ms 1048576 KB Output isn't correct
4 Incorrect 617 ms 823740 KB Output isn't correct
5 Incorrect 773 ms 997272 KB Output isn't correct
6 Runtime error 730 ms 1048576 KB Execution killed with signal 9
7 Incorrect 300 ms 786000 KB Output isn't correct
8 Incorrect 299 ms 784724 KB Output isn't correct
9 Incorrect 353 ms 755028 KB Output isn't correct
10 Incorrect 315 ms 754004 KB Output isn't correct
11 Incorrect 341 ms 785288 KB Output isn't correct
12 Incorrect 328 ms 755172 KB Output isn't correct
13 Incorrect 479 ms 804188 KB Output isn't correct
14 Incorrect 412 ms 784248 KB Output isn't correct
15 Incorrect 416 ms 780884 KB Output isn't correct
16 Incorrect 383 ms 777048 KB Output isn't correct
17 Incorrect 712 ms 873296 KB Output isn't correct
18 Incorrect 748 ms 845904 KB Output isn't correct
19 Incorrect 614 ms 823892 KB Output isn't correct
20 Incorrect 549 ms 833552 KB Output isn't correct
21 Incorrect 953 ms 951632 KB Output isn't correct
22 Incorrect 876 ms 997380 KB Output isn't correct
23 Incorrect 1113 ms 975696 KB Output isn't correct
24 Incorrect 1094 ms 972884 KB Output isn't correct
25 Runtime error 1127 ms 1048576 KB Execution killed with signal 9
26 Runtime error 682 ms 1048576 KB Execution killed with signal 9
27 Runtime error 775 ms 1048576 KB Execution killed with signal 9
28 Runtime error 794 ms 1048576 KB Execution killed with signal 9
29 Runtime error 850 ms 1048576 KB Execution killed with signal 9
30 Runtime error 797 ms 1048576 KB Execution killed with signal 9
31 Runtime error 816 ms 1048576 KB Execution killed with signal 9
32 Runtime error 821 ms 1048576 KB Execution killed with signal 9