제출 #199647

#제출 시각아이디문제언어결과실행 시간메모리
199647ZwariowanyMarcinTeoretičar (COCI18_teoreticar)C++14
13 / 130
1397 ms221184 KiB
#include <bits/stdc++.h> #define fi first #define se second #define mp make_pair #define ss(x) (int) x.size() #define pb push_back #define LL long long #define LD long double #define cat(x) cerr << #x << " = " << x << endl #define FOR(i, j, n) for(int i = j; i <= n; ++i) #define boost cin.tie(0), ios_base::sync_with_stdio(0); using namespace std; const int nax = 2e5 + 111; int L, R, m; int a, b; struct gao { int a, b, id; }; vector <gao> x; vector <gao> tyt; int n; int color = 1; vector <pair<int, int>> v[nax]; int deg[nax]; int ans[nax]; bool odw[nax]; int wsk[nax]; void dfs(int u, int par = 0, int p = -1, int id = -1) { while (wsk[u] < ss(v[u])) { pair<int, int> it = v[u][wsk[u]]; wsk[u]++; if (odw[it.se]) continue; odw[it.se] = 1; dfs(it.fi, (par + 1) % 2, u, it.se); } if (u > n || p > n || id == -1) return; tyt.pb({min(u, p), max(u, p), id}); } void solve(vector <gao> y) { vector <gao> Left, Right; for (auto &it : y) if (it.a > it.b) swap(it.a, it.b); for (auto it : y) { deg[it.a]++; deg[it.b]++; } int MAX = 0; for (auto it : y) { MAX = max(MAX, deg[it.a]); MAX = max(MAX, deg[it.b]); } if (MAX == 1) { for (auto it : y) { ans[it.id] = color; deg[it.a] = 0; deg[it.b] = 0; } color++; return; } int nowe = m + 1; for (auto it : y) { v[it.a].pb({it.b, it.id}); v[it.b].pb({it.a, it.id}); } for (auto it : y) { if (ss(v[it.a]) % 2 == 1) { v[it.a].pb({n + 1, nowe}); v[n + 1].pb({it.a, nowe++}); } if (ss(v[it.b]) % 2 == 1) { v[it.b].pb({n + 2, nowe}); v[n + 2].pb({it.b, nowe++}); } } if (ss(v[n + 1]) % 2 == 1) { v[n + 1].pb({n + 2, nowe}); v[n + 2].pb({n + 1, nowe++}); } assert(ss(v[n + 1]) % 2 == 0); assert(ss(v[n + 2]) % 2 == 0); Left.clear(); Right.clear(); tyt.clear(); for (auto it : y) { dfs(it.a); dfs(it.b); } dfs(n + 1); dfs(n + 2); for (int i = 0; i < ss(tyt); ++i) { if (tyt[i].b > n) continue; if (i & 1) Left.pb(tyt[i]); else Right.pb(tyt[i]); } /*cat(ss(y)); for (auto it : y) { cat(it.a); cat(it.b); cat(it.id); printf ("\n"); } printf ("\n"); cat("L"); for (auto it : Left) printf ("%d %d\n", it.a, it.b); cat("R"); for (auto it : Right) printf ("%d %d\n", it.a, it.b); printf ("\n\n"); */ assert(ss(Left) > 0); assert(ss(Right) > 0); for (auto it : y) { v[it.a].clear(); v[it.b].clear(); wsk[it.a] = 0; wsk[it.b] = 0; deg[it.a] = 0; deg[it.b] = 0; odw[it.id] = 0; } v[n + 1].clear(); v[n + 2].clear(); wsk[n + 1] = 0; wsk[n + 2] = 0; for (int i = m + 1; i <= nowe; ++i) odw[i] = 0; solve(Left); solve(Right); } int main() { scanf ("%d %d %d", &L, &R, &m); n = L + R; for (int i = 1; i <= m; ++i) { scanf ("%d%d", &a, &b); b += L; x.pb({a, b, i}); } solve(x); printf ("%d\n", color - 1); for (int i = 1; i <= m; ++i) printf ("%d\n", ans[i]); return 0; }

컴파일 시 표준 에러 (stderr) 메시지

teoreticar.cpp: In function 'int main()':
teoreticar.cpp:165:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d %d %d", &L, &R, &m);
  ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
teoreticar.cpp:168:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%d%d", &a, &b);
   ~~~~~~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...