Submission #1289373

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289373		dragst	Tracks in the Snow (BOI13_tracks)	C++20	26.35 / 100	853 ms	1114112 KiB

tracks

#include <bits/stdc++.h>
#define pll pair<long long, long long>
using namespace std;

char a[4005][4005];
long long p[2000005], r[2000005], dp[2000005], pre[2000005], check[4005][4005], check2[2000005];
queue<pll> q;
queue<long long> q2;
pll p2;
vector<long long> v, adj[2000005];

void makeset(long long x)
{
    p[x]=x;
}

long long findset(long long x)
{
    if (p[x]!=x) {p[x]=findset(p[x]);};
    return p[x];
}

void unionsets(long long x, long long y)
{
    x=findset(x);
    y=findset(y);
    if (x!=y)
    {
        if (r[x]<r[y]) {swap(x, y);};
        p[y]=x;
        if (r[x]==r[y]) {r[x]++;};
    };
}

int main()
{
    long long n, m, i, j;
    cin >> n >> m;
    for (i=1; i<=n; i++)
    {
        for (j=1; j<=m; j++)
        {
            cin >> a[i][j];
            if (a[i][j]=='.') {continue;};
            makeset((i-1)*m+j);
            if (i>1 && a[i-1][j]==a[i][j]) {unionsets((i-1)*m+j, (i-2)*m+j);};
            if (j>1 && a[i][j-1]==a[i][j]) {unionsets((i-1)*m+j, (i-1)*m+j-1);};
        };
    };
    q.push(make_pair(1, 1));
    check[1][1]=1;
    check2[findset(1)]=1;
    while (!q.empty())
    {
        p2=q.front();
        q.pop();
        i=p2.first; j=p2.second;
        if (i>1 && a[i-1][j]!='.' && !check[i-1][j])
        {
            if (a[i-1][j]!=a[i][j] && !check2[findset((i-2)*m+j)]) {adj[findset((i-2)*m+j)].push_back(findset((i-1)*m+j)); check2[findset((i-2)*m+j)]=1;};
            q.push(make_pair(i-1, j));
            check[i-1][j]=1;
        };
        if (j>1 && a[i][j-1]!='.' && !check[i][j-1])
        {
            if (a[i][j-1]!=a[i][j] && !check2[findset((i-1)*m+j-1)]) {adj[findset((i-1)*m+j-1)].push_back(findset((i-1)*m+j)); check2[findset((i-1)*m+j-1)]=1;};
            q.push(make_pair(i, j-1));
            check[i][j-1]=1;
        };
        if (i<n && a[i+1][j]!='.' && !check[i+1][j])
        {
            if (a[i+1][j]!=a[i][j] && !check2[findset(i*m+j)]) {adj[findset(i*m+j)].push_back(findset((i-1)*m+j)); check2[findset(i*m+j)]=1;};
            q.push(make_pair(i+1, j));
            check[i+1][j]=1;
        };
        if (j<m && a[i][j+1]!='.' && !check[i][j+1])
        {
            if (a[i][j+1]!=a[i][j] && !check2[findset((i-1)*m+j+1)]) {adj[findset((i-1)*m+j+1)].push_back(findset((i-1)*m+j)); check2[findset((i-1)*m+j+1)]=1;};
            q.push(make_pair(i, j+1));
            check[i][j+1]=1;
        };
    };
    for (i=1; i<=n; i++)
    {
        for (j=1; j<=m; j++)
        {
            if (a[i][j]=='.') {continue;};
            v.push_back(findset((i-1)*m+j));
        };
    };
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    for (auto x: v)
    {
        for (auto y: adj[x]) {pre[y]++;};
    };
    for (auto x: v)
    {
        if (pre[x]==0) {q2.push(x); dp[x]=1;};
    };
    while (!q2.empty())
    {
        i=q2.front();
        q2.pop();
        for (auto x: adj[i])
        {
            dp[x]=max(dp[x], dp[i]+1);
            pre[x]--;
            if (pre[x]==0) {q2.push(x);};
        };
    };
    cout << dp[findset(1)];
}

• Subtask 1: 6.6667 / 30
• Subtask 2: 19.6875 / 70