In 843E - Maximum Flow it is stated in the tutorial:

"For an each edge from original graph without any flow let's create a new edge with the same direction and c = INF carrying capacity. For every edge with a flow let's create two edges: the first one with the same direction and c = 1 capacity and the second edge with reversed direction and c = INF."

Why do I need the second edge with reversed direction and c=INF for the edge with flow? I know it affect the min-cut but I cannot find any specific example. In fact, in one of tourist submissions 29956114, he didn't add this edge and still get AC.

  int n, m, st, fin;
  scanf("%d %d %d %d", &n, &m, &st, &fin);
  st--; fin--;
  flow_graph <int> g(n, st, fin);
  for (int i = 0; i < m; i++) {
    scanf("%d %d %d", from + i, to + i, flag + i);
    from[i]--; to[i]--;
    if (flag[i] == 1) {
      g.add(from[i], to[i], 1, inf);
    } else {
      g.add(from[i], to[i], inf, 0);
    }
  }
  cout << g.max_flow() << endl;
  vector <bool> cut = g.min_cut();
  flow_graph <int> g2(n + 2, n, n + 1);
  for (int i = 0; i < m; i++) {
    if (!flag[i]) {
      continue;
    }
    g2.add(n, to[i], 1, 0);
    g2.add(from[i], n + 1, 1, 0);
    g2.add(from[i], to[i], inf - 2, 0);
  }
  g2.add(fin, st, inf, 0);
  g2.max_flow();

Please give me some ideas to solve this problem. My teacher hints that this problem is solved using line sweep but I'm still not able to build any solution base on that concept.

This is the problem statement:

Archaeologists of Olympia planet have just discovered the remnant of an ancient city. The remnant consists of N fortresses and M walls which connect a pair of fortresses. In a simple model, each fortress is considered as a point in the plane, while the walls are the lines connect these points. Two arbitrary lines have no intersection except at the endpoints which are the fortresses.

In order to study the city, K archaeologists is standing at different positions in the city. There positions are demonstrated as points in the plane. No archaeologist stands on the wall or fortress. Telephones are not exist in the ancient city, so the only way for the archaeologists to communicate is to walk to each other. Two people can communicate if they are able to come to the same point in the plain and their path is not intersect with any walls or fortresses. The path is not restricted to be straight.

Base on the information about the fortresses, walls and archaeologists, calculate the number of pairs of archaeologist that can meet each other.

Input

• The first line is 3 positive integer N, M and K (1 ≤ N ≤ 5·10⁴, 1 ≤ M ≤ 10⁵, 1 ≤ K ≤ 5·10⁴) — the number of fortresses, walls and archaeologists.

• The i line in the next N lines contains of 2 integer (each has their absolute value does not exceed 10⁶) is the coordinate of the i fortresses.

• Each line in the next M lines contain of 2 integer are the indices of 2 fortresses which have a wall connect them.

• Each line in the next K lines contain of 2 integer (each has their absolute value does not exceed 10⁶) is the coordinate of a archaeologist.

Output

The number of pairs of archaeologist that can meet each other.

Example

Input

4 5 7
0 0
10 0
10 10
0 10
1 2
2 3
3 4
4 1
4 2
1 1
2 2
9 9
8 8
-1 -1
-5 -5
100 100

Output

5

Today I submit the solution for : Problem I — Gym 101061 using scanf/printf and it gives me TLE (Time limit exceeded on test 2). This is my solution:

#include <bits/stdc++.h>
using namespace std;

const int MAX = 1e5 + 10;

int T;
char s1[MAX], s2[MAX];
int c1[30], c2[30];

int main(){
    scanf("%d", &T);
    while(T--){
        scanf("%s", s1);
        scanf("%s", s2);

        memset(c1, 0, sizeof(c1));
        memset(c2, 0, sizeof(c2));

        for(int i = 0; i < (int)strlen(s1); i++) c1[s1[i] - 'a']++;
        for(int i = 0; i < (int)strlen(s2); i++) c2[s2[i] - 'a']++;

        int res = 0;
        for(int i = 0; i < 26; i++) res += abs(c1[i] - c2[i]);

        printf("%d\n", res);
    }
}

But when I change to cin/cout, I get AC in 15ms. This is the second solution:

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'

int T;
string s1, s2;
int c1[30], c2[30];

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> T;
    while(T--){
        cin >> s1 >> s2;

        memset(c1, 0, sizeof(c1));
        memset(c2, 0, sizeof(c2));

        for(int i = 0; i < (int)s1.size(); i++) c1[s1[i] - 'a']++;
        for(int i = 0; i < (int)s2.size(); i++) c2[s2[i] - 'a']++;

        int res = 0;
        for(int i = 0; i < 26; i++) res += abs(c1[i] - c2[i]);

        cout << res << endl;
    }
}

I'm used to scanf/printf because I think it's fast but this time brings a huge doubt. Can anybody explain this for me? Is it because in cin/cout solution I use cin.tie(NULL)?

Could someone give me some advice?

In Pascal, I usually see people using one-based index.
But in C++, everyone prefers zero-based index.

I know each has its own advantages.
I find it hard to use one-based index in forming formulas because I have to add and subtract 1 all the times.
In zero-based index, this is not a problem but sometimes because the first element is zero, so if I want to use some initial values I have to set it to negative, for examples -1, but the issue is I have to check the overflow of the value because I cannot index negative value.

I want to get used to just one type, so anybody can give me more ideas before I do it?
Thank you.