Submission #2835

#TimeUsernameProblemLanguageResultExecution timeMemory
2835mh5664간선 파괴 (GA5_destroy)C++98
25 / 100
2500 ms2676 KiB
#include <stdio.h> #include <vector> using namespace std; const int MAXN = 700; vector<pair<int,int> > data[MAXN + 1]; int q[MAXN + 1]; int r = -1, f = -1; bool ch[MAXN + 1]; int main () { int n, m; scanf ("%d %d", &n, &m); for (int i = 0; i < m; ++i) { int x, y; scanf ("%d %d", &x, &y); data[x - 1].push_back (make_pair (y - 1, i + 1)); data[y - 1].push_back (make_pair (x - 1, i + 1)); } int k; scanf ("%d", &k); for (int i = 0; i < k; ++i) { int x, y; scanf ("%d %d", &x, &y); int sol = 0; for (int i = 0; i < n; ++i) { if (!ch[i]) { int j; ++sol; r = f = -1; q[++r] = i; ch[i] = true; while (r > f) { j = q[++f]; for (int k = 0; k < data[j].size (); ++k) { if (x <= data[j][k].second && data[j][k].second <= y) continue; if (!ch[data[j][k].first]) { ch[data[j][k].first] = true; q[++r] = data[j][k].first; } } } } } printf ("%d\n", sol); for (int i = 0; i < n; ++i) { ch[i] = false; } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...