Submission #1093067

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093067		mm77	Tracks in the Snow (BOI13_tracks)	C++14	0 / 100	1377 ms	1048576 KiB

tracks

#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
• Subtask 2: 0 / 70