Submission #641618

#	Time	Username	Problem	Language	Result	Execution time	Memory
641618		danikoynov	Olympic Bus (JOI20_ho_t4)	C++14	21 / 100	57 ms	2400 KiB

ho_t4

/**
 ____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|

**/

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const int maxn = 210, maxm = 50010;

struct edge
{
    int v, u, c, d;
}e[maxm];

bool cmp_d(edge e1, edge e2)
{
    return e1.d < e2.d;
}

int n, m, used[maxn], path[maxn][maxn], cap[maxn][maxn];
void solve()
{
    cin >> n >> m;
    bool czero = true;
    for (int i = 1; i <= m; i ++)
    {
        cin >> e[i].v >> e[i].u >> e[i].c >> e[i].d;
        path[e[i].v][e[i].u] = 1;
        cap[e[i].v][e[i].u] ++;
        if (e[i].c != 0)
            czero = false;
    }

    if (czero)
    {
        sort(e + 1, e + m + 1, cmp_d);

        for (int i = 1; i <= n; i ++)
            path[i][i] = 1;
    for (int k = 1; k <= n; k ++)
        for (int i = 1; i <= n; i ++)
            for (int j = 1; j <= n; j ++)
        {
            if (path[i][k] == 1 && path[k][j] == 1)
            {
                ///cout << i << " " << k << " " << j << endl;
                path[i][j] = 1;
            }
        }

        if (path[1][n] == 1 && path[n][1] == 1)
        {
            cout << 0 << endl;
            return;
        }

        if (path[1][n] == 0 && path[n][1] == 0)
        {
            bool tf = false;
            for (int i = 1; i <= m; i ++)
            {
                int v = e[i].v, u = e[i].u;
                ///cout << v << " " << u << endl;
                ///cout << path[1][u] << " " << path[v][n] << " " << path[n][u] << " " << path[v][1] << endl;
                if (path[1][u] == 1 && path[v][n] == 1 &&
                    path[n][u] == 1 && path[v][1] == 1)
                {
                    cout << e[i].d << endl;
                    tf = true;
                    break;
                }
            }
            if (!tf)
            {
                cout << -1 << endl;
            }
            return;
        }

        if (path[1][n] == 0)
        {
            bool tf = false;
            for (int i = 1; i <= m; i ++)
            {
                int v = e[i].v, u = e[i].u;
                if (path[1][u] == 1 && path[v][n] == 1)
                {
                    cap[v][u] --;
                    cap[u][v] ++;

                    for (int j = 1; j <= n; j ++)
                        used[j] = 0;
                    queue < int > q;
                    q.push(n);
                    used[n] = 1;
                    while(!q.empty())
                    {
                        int cur = q.front();
                        q.pop();
                        for (int j = 1; j <= n; j ++)
                            if (cap[cur][j] > 0 && !used[j])
                        {
                            used[j] = 1;
                            q.push(j);
                        }
                    }
                    if (used[1] == 1)
                    {
                        cout << e[i].d << endl;
                        tf = true;
                        break;
                    }
                    cap[v][u] ++;
                    cap[u][v] --;
                }
            }
            if (!tf)
            {
                cout << -1 << endl;
            }
            return;

        }

        if (path[n][1] == 0)
        {
            bool tf = false;
            for (int i = 1; i <= m; i ++)
            {
                int v = e[i].v, u = e[i].u;
                if (path[n][u] == 1 && path[v][1] == 1)
                {
                    cap[v][u] --;
                    cap[u][v] ++;

                    for (int j = 1; j <= n; j ++)
                        used[j] = 0;
                    queue < int > q;
                    q.push(1);
                    used[1] = 1;
                    while(!q.empty())
                    {
                        int cur = q.front();
                        q.pop();
                        for (int j = 1; j <= n; j ++)
                            if (cap[cur][j] > 0 && !used[j])
                        {
                            used[j] = 1;
                            q.push(j);
                        }
                    }
                    if (used[n] == 1)
                    {
                        cout << e[i].d << endl;
                        tf = true;
                        break;
                    }
                    cap[v][u] ++;
                    cap[u][v] --;
                }
            }
            if (!tf)
            {
                cout << -1 << endl;
            }
            return;
        }

    }

}

int main()
{
    solve();
    return 0;
}

/**
4 4
2 1 0 4
3 1 0 1
3 4 0 2
1 4 0 1
*/

Compilation message (stderr)

ho_t4.cpp: In function 'void solve()':
ho_t4.cpp:54:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   54 |     for (int k = 1; k <= n; k ++)
      |     ^~~
ho_t4.cpp:65:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   65 |         if (path[1][n] == 1 && path[n][1] == 1)
      |         ^~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 11
• Subtask 3: 21 / 21
• Subtask 4: 0 / 63