5 8
2 3
1 2
2 5
1 4
1 5
3 4
3 4
4 4
8
7 6 8 2 3 4 5 1
> 1 1 1 1 2 3 4 5

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