NutelIa's blog

By NutelIa, history, 7 years ago, In English

I am learning Stoer-Wagner algorithm and I found this implementation:
https://en.wikipedia.org/wiki/Stoer%E2%80%93Wagner_algorithm
It states the cut is incorrect but I don't understand why, as it seems correct to me and I don't understand the case it explains. Why is it wrong?

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By NutelIa, history, 7 years ago, In English

I sent a code for problem C in this contest: http://codeforces.net/gym/100026 and I got runtime error (I didn't have runtime error in my computer nor in custom invocation). I couldn't find out where the error came from so I simplified my code (knowing it would get WA) to find the source. One of the last codes I sent was:

#include <bits/stdc++.h>

using namespace std;
struct punt{
	int x,y;
};
typedef vector < punt > VE;
int n,k;
VE mines, pals;
int main(){
	cin >> n >> k;
	pals = VE(n);
	mines = VE(k);
	for(int i = 0; i < n; i++) {
		int x,y;
		cin >> x >> y;
		pals[i] = {x,y};
	}
	for(int i = 0; i < k; i++) {
		int x,y;
		cin >> x >> y;
		mines[i] = {x,y};
	}
	cout << "** " << mines[0].x << ' ' << mines[0].y << endl;
}

And I still got runtime error. Checking the test case with a friend who has "coach mode" enabled I could find out k != 0 (as it corresponds to first test case in the sample). The source of the runtime error is the access to mines[0] but I don't understand why. Moreover, when I change the last few lines to these ones:

for(int i = 0; i < k; i++) {
	int x,y;
	cin >> x >> y;
	mines[i] = {x,y};
	cout << "** " << mines[i].x << ' ' << mines[i].y << endl;
}

I don't get runtime error. Instead this message is shown

alt text

Can someone help me? Is it a CF problem or mine?

Full text and comments »

  • Vote: I like it
  • -3
  • Vote: I do not like it