Check your "MAXN" constant

I`m using vector of segments.
Everything is pretty fast, All the tests I could think of work correctly.

EDIT:
Finally, got a pretty good AC - Time: 0.234, Memory: 5 032 KB.
(The problem was that I was not monitoring for segments getting empty)

Edited by author 12.04.2023 23:40

Дайте тесты, пожалуйста

I firstly tried to solve it with Ford-Bellman algorithm, but got TL and could not make it pass. Then I found here https://e-maxx.ru/algo/min_cost_flow Levit algorithm, and it passed.

A new constraint on the input added: “It is guaranteed that any two distinct intersection or touch points of the cutting circles lay at the distance of at least 10^-3.” The tests not satisfying this constraint were corrected or removed. Some new tests were added at the same time. The time limit was adjusted to 1 sec.

All solutions have been rejudged. 23 authors lost, and 13 other authors gained the solved status for the problem.

Im an idiot
I wrote "Saturtay" instead Saturday

Edited by author 10.04.2023 02:46

After some failed attempts with O(n)=n*n/2, finally I found an O(n)=n solution.
In plain C, it took 0.09s and 1.5Mb. (just from curiosity tried the same with C# - 14MB used RAM :))

The arrays of X and Y coordinates can be sorted independently from each other.

So basically, this input:
3
1 3
2 1
3 2
will have exactly the same result (which is 2) as
3
1 1
2 2
3 3

My bad accepted, best Go solution to date

Edited by author 06.04.2023 19:36

Try this test:

-10 -1 1
-1 8 1
-7 2 1
3

Answer: 14.38

who has ideas, what test it is?

such interesting problem

Help please:
Test 23, whats wrong, what test should chek?

def sieve(n):
    lis = list(range(n + 1))
    lis[1] = 0
    for i in lis:
        if i > 1:
            for j in range(i + i, len(lis), i):
                lis[j] = 0
    return [i for i in lis if i != 0]
c = sieve(200)
a = int(input())
if a == 0:
    print('No')
i = 0
b = []
e = 0
while a != 1:
    if a%5 != 0 and a%2 != 0 and a%3 != 0:
        e +=1
        break

    elif a % c[i] == 0:
        a /= c[i]
        b.append(c[i])
        continue

    else:
        i += 1
d = str(len(b))
if  len (b) == 20 or (len (b) == 19 and e != 0):
    print('Yes')
else:
    print('No')

such data:
3
aaa
aaa

the answer is 0 rather than 3

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.