Submission #356295

#TimeUsernameProblemLanguageResultExecution timeMemory
356295parsabahramiSenior Postmen (BOI14_postmen)C++17
55 / 100
608 ms78148 KiB
// Call my Name and Save me from The Dark #include <bits/stdc++.h> using namespace std; typedef long long int ll; typedef pair<int, int> pii; #define SZ(x) (int) x.size() #define F first #define S second const int N = 5e5 + 10; int P[N], R[N], L[N], M[N], ptr[N], from[N], to[N], n, m; vector<int> adj[N], tr; void tour(int v) { while (ptr[v] < SZ(adj[v])) { int id = adj[v][ptr[v]++]; int u = from[id] ^ v ^ to[id]; if (!M[id]) M[id] = 1, tour(u); } tr.push_back(v); } int Find(int v) { return !~P[v] ? v : P[v] = Find(P[v]); } void Union(int u, int v) { u = Find(u), v = Find(v); if (u == v) return; if (L[u] > L[v]) swap(u, v); P[u] = v, L[v] = L[v] + L[u], R[v] = max(R[u], R[v]); } int main() { memset(P, -1, sizeof P); scanf("%d%d", &n, &m); for (int i = 1; i <= m; i++) { scanf("%d%d", &from[i], &to[i]); adj[from[i]].push_back(i); adj[to[i]].push_back(i); } tour(1); for (int i = 0; i <= SZ(tr); i++) L[i] = 1, R[i] = i; memset(M, -1, sizeof M); for (int i = 0; i < SZ(tr) && L[Find(0)] != SZ(tr); i = R[Find(i + 1)]) { //printf("i %d\n", i); if (~M[tr[i]]) { int l = M[tr[i]]; for (int j = M[tr[i]]; j < i; j = R[Find(j + 1)]) { //printf("j %d\n", j); printf("%d ", tr[j]), M[tr[j]] = -1; } printf("\n"); for (int j = l; j < i; j = R[Find(j + 1)]) { Union(j, R[Find(j + 1)]); } M[tr[i]] = i; } else M[tr[i]] = i; } return 0; }

Compilation message (stderr)

postmen.cpp: In function 'int main()':
postmen.cpp:37:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   37 |     scanf("%d%d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~
postmen.cpp:39:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   39 |         scanf("%d%d", &from[i], &to[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...