제출 #69064

#제출 시각아이디문제언어결과실행 시간메모리
69064GoodMin-max tree (BOI18_minmaxtree)C++11
22 / 100
459 ms26976 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #define ff first #define ss second #define Maxn 70009 #define ll long long #define pb push_back #define Inf 1000000009 #define ppb() pop_back() #define pii pair <int , int> #define mid(x, y) (x + y) / 2 #define all(x) x.begin(),x.end() #define llInf 1000000000000000009 #define tr(i, c) for(__typeof(c).begin() i = (c).begin() ; i != (c).end() ; i++) using namespace std; using namespace __gnu_pbds; typedef tree <int, null_type, less <int>, rb_tree_tag, tree_order_statistics_node_update> order; int n, q; int lvl[Maxn]; int E[Maxn][2]; int P[Maxn][2]; int mat[Maxn][20]; vector <int> adj[Maxn]; vector <pair <int, pair <int, pii> > > A[2]; map <int, int> mp; map <int, bool> mp1; void dfs (int nd, int p, bool d) { mat[nd][0] = p; lvl[nd] = lvl[p] + 1; for (auto i: adj[nd]) if (i != p) { if (d == 1) { int x = E[i][0], y = E[i][1]; if (mp[x] and mp[y]) { mp[x] --, mp[y] --; if (!mp1[x] and !mp1[y]) { if (mp[x] < mp[y]) mp1[x] = 1, printf ("%d %d %d\n", nd, i, x); else mp1[y] = 1, printf ("%d %d %d\n", nd, i, y); } else if (!mp1[x]) mp1[x] = 1, printf ("%d %d %d\n", nd, i, x); else mp1[y] = 1, printf ("%d %d %d\n", nd, i, y); } else if (mp[x]) mp1[x] = 1, mp[x] --, printf ("%d %d %d\n", nd, i, x); else if (mp[y]) mp1[y] = 1, mp[y] --, printf ("%d %d %d\n", nd, i, y); else printf ("%d %d 0\n", nd, i); } dfs (i, nd, d); } } void build () { for (int i = 1; i <= 18; i++) for (int j = 1; j <= n; j++) if (mat[j][i - 1] != -1) mat[j][i] = mat[mat[j][i - 1]][i - 1]; } int LCA (int a, int b) { if (lvl[a] < lvl[b]) swap (a, b); for (int i = 18; i >= 0; i--) if (lvl[mat[a][i]] >= lvl[b]) a = mat[a][i]; if (a == b) return a; for (int i = 18; i >= 0; i--) if (mat[a][i] != -1 and mat[a][i] != mat[b][i]) a = mat[a][i], b = mat[b][i]; return mat[a][0]; } int dsu (int x, bool d) { if (P[x][d] == x) return x; return P[x][d] = dsu (P[x][d], d); } void solve (int x, int y, int z, bool d) { x = dsu (P[x][d], d); if (lvl[x] <= lvl[y]) return; mp[z] ++; E[x][d] = z; if (mat[x][0] != -1) P[x][d] = dsu (mat[x][0], d); x = P[x][d]; solve (x, y, z, d); } int main () { //freopen ("file.in", "r", stdin); //freopen ("file.out", "w", stdout); //srand ((unsigned) time ( NULL )); //int randomNumber = rand() % 10 + 1; scanf ("%d", &n); for (int i = 1; i < n; i++) { int u, v; scanf ("%d%d", &u, &v); adj[u].pb (v); adj[v].pb (u); P[i][0] = P[i][1] = i; } P[n][0] = P[n][1] = n; memset (mat, -1, sizeof (mat)); dfs (1, -1, 0); build (); scanf ("%d", &q); for (int i = 1; i <= q; i++) { char c; int x, y, z; scanf (" %c%d%d%d", &c, &x, &y, &z); int l = LCA (x, y); if (c == 'M') A[0].pb ({z, {l, {x, y}}}); else A[1].pb ({z, {l, {x, y}}}); } sort (all (A[0])); sort (all (A[1])); reverse (all (A[1])); for (auto i: A[0]) { solve (i.ss.ss.ff, i.ss.ff, i.ff, 0); solve (i.ss.ss.ss, i.ss.ff, i.ff, 0); } for (auto i: A[1]) { solve (i.ss.ss.ff, i.ss.ff, i.ff, 1); solve (i.ss.ss.ss, i.ss.ff, i.ff, 1); } dfs (1, -1, 1); return 0; }

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

minmaxtree.cpp: In function 'int main()':
minmaxtree.cpp:124:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d", &n);
  ~~~~~~^~~~~~~~~~
minmaxtree.cpp:127:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%d%d", &u, &v);
   ~~~~~~^~~~~~~~~~~~~~~~
minmaxtree.cpp:140:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d", &q);
  ~~~~~~^~~~~~~~~~
minmaxtree.cpp:146:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf (" %c%d%d%d", &c, &x, &y, &z);
   ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...