Instead of doing the cuts in the order given in the input,
I found it easier to do it in reverse order, so we get merging instead of cutting.

Edited by author 29.03.2023 21:05

#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
#define int long long
#define mod 1000000007

#define maxn 10010
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define inf 100000000000

vector<pair<int, int>> adj[maxn];
int n, m;

// struct node //for edges
// {
//     int pos, dir, dist;

//     node(){};
//     node(int _pos, int _dir)
//     {
//         pos = _pos;
//         dir = _dir;
//     }
// };

int go(int s, int e)
{

    int dist[maxn][2];
    for(int i=0; i<maxn; i++)
    {
        for(int j=0; j<=1; j++)
        {
            dist[i][j] = inf;
        }
    }

    deque<pair<int, int>> q; //pair->{node, edgedir}

    //making direction list here,
    q.push_back({s, 0}); //0->outgoing to node s
    dist[s][0] = 0;
    q.push_back({s, 1}); //1->incoming from node s
    dist[s][1] = 0;

    while(!q.empty())
    {
        pair<int, int> cur = q.front();
        //node
        int v = cur.first;
        int dir = cur.second;
        //dist
        int dv = dist[v][dir];

        //guarenteed that shortest dist till cur node has been calc already

        q.pop_front();
        //if(dv == inf) break;

        if(cur.first == e) return dv; //gauarenteed via djikstra that this willbe minimest

        //relax all the neighbours, and as you relax one , push into minheap the nodes
        for(auto it: adj[v])
        {
            int to = it.fi;
            int dir2 = it.se;
            //previous
            //note that for type edge dir, you have relax for all neighbouring nodes
            int dist2=0;
            if(dir2 == dir)
            {
                dist2 = dist[v][dir2];
                //dist[to][dir2] = min( dist[to][dir2], dist[v][dir2] );
            }
            else dist2 = dist[v][dir] + 1;
               // dist[to][dir2] = min( dist[to][dir2], dist[v][dir] + 1);


            //only relax and add to queue, if less than prev distance to this node
            if(dist2 < dist[to][dir2])
            {
                if(dist2 <= dv) //less than equal to cur_dist
                    q.push_front({to, dir2});
                else
                    q.push_back({to, dir2});

                dist[to][dir2] = dist2;

            }


        }
    }

    return -1;


}

void solve()
{
    cin>>n>>m;

    for(int i=1;i<=m;i++)
    {
        int x, y; cin>>x>>y;
        adj[x].pb({y, 0});
        adj[y].pb({x, 1});
    }
    int s, e; cin>>s>>e;
    //cout<<"hi";
    int ans = go(s, e);
    cout<<ans<<endl;


}

signed main()
{
    int t=1;
    //cin>>t;
    while(t--)
    {
        solve();
    }
    return 0;
}

Я решил задачу с помощью графа, где вершинки - состояния ёмкостей,и рассмотрел из очередного состояния все переходы, запоминая те состояния ,где уже был.
Но я никак не могу оценить кол-во возможных состояний. Может кто-нибудь подскажет как оценить? Самая грубая оценка - у нас есть числа a,b,c>=0 и a+b+c=N(для случая,когда не подливаем и не выливаем-в этом случае сумма константа). Тогда количество таких чисел O(N^3),но это ужасная оценка.

First I used Kruskal algo but got WA9 verdict.
My program didn't give right answer for next test:
4 1
4
0    1    1    100000
1    0    1    100000
1    1    0    100000
100000    100000    100000    0
right answer:
100002

Implementation of Prim algo gave the correct answer at last.

input:
2
b 1
a 1

2
a
b

output:
a
[empty]
b

hope can help you!
GOOD LUCK!

New tests were added. All accepted solution were rejudged, ~4% of them lost their accepted status

не могу найти ошибку,возможно ли узнать какие числа вбивает 8-й тест?

Check if your input correctly outputs the last word, if the last character is latin.
The first test ends with a .

Edited by author 21.03.2023 18:29

input:
6 3
8
1 0
2 0
3 0
4 0
5 1
7 1
10 1
12 1

output:
No reason
1 10
2 5
3 12
4 7

What is in test 3?????

//Don't ask me. I don't know. Just work. If anybody can tell me why   for (int i = k + 7; i >= 0; i--)   and why we needn't n%k - Please, tell! I don't understand.

using System;

namespace ConsoleApp32
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] vvod = Console.In.ReadLine().Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries);
            int n = int.Parse(vvod[0]);
            string k1 = vvod[1];
            int k = k1.Length;
            int q = 1;

            for (int i = k + 7; i >= 0; i--)
                {
                    int t;
                    t = n - i * k;
                    if (t > 0) q *= t;
                }
            Console.WriteLine(q);
        }
    }
}

Edited by author 13.01.2018 23:49

Make sure your code can choose devices other than the 1st one from the list...

Why does this code throw a runtime error?
Everything is right!!

from sys import stdin
pocht_1 = ["A", "P", "O", "R"]
pocht_2 = ["B", "M", "S"]
pocht_3 = ["D", "G", "J", "K", "T", "W"]
count = 0
mesto = 1
for i in sys.stdin.split("\n")[1:]:
    if i[0] in pocht_1:
        if mesto == 3:
            count += 2
        elif mesto == 2:
            count += 1
        mesto = 1
    elif i[0] in pocht_2:
        if mesto == 1:
            count += 1
        elif mesto == 3:
            count += 1
        mesto = 2
    else:
        if mesto == 1:
            count += 2
        elif mesto == 2:
            count += 1
        mesto = 3
print(count)

1 2 0 0 0 0 0 0
3 3 0 0 0 0 0 0
0 0 0 0 0 0 0 0
2

2.24

My solution is 20 lines.
Easy problem.

All operations except clone work O(1) in my program, but clone works in O(n). Despite that fact, my solution works in 0.218s

Read problem statement more closely. The graph can be disconnected.