# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
95459 | 2019-02-01T11:01:57 Z | mzhao | Praktični (COCI18_prakticni) | C++11 | 445 ms | 31740 KB |
#include <bits/stdc++.h> using namespace std; #ifdef DEBUG #define D(x...) printf(x) #else #define D(x...) #endif #define x first #define y second #define MN 100100 int N, M; struct End { int n, w, i; }; vector<End> adj[MN]; int dep[MN]; bool vis[MN]; vector<int> st; bool visEdge[MN]; int valEdge[MN]; set<int> vals; bool bitAdj[32][32], bitNo[32][32], bitVis[32], bv[32]; int comp[32], compVal[32], nc; set<int> applyto[32]; void dfs(int n, int d) { vis[n] = 1; dep[n] = d; for (End i : adj[n]) if (!vis[i.n]) { st.push_back(st.back() ^ i.w); dfs(i.n, d+1); st.pop_back(); } else if (dep[i.n] < d) { int val = st.back() ^ st[dep[i.n]] ^ i.w; if (val) { visEdge[i.i] = 1; valEdge[i.i] = val; vals.insert(val); } } } void dfs2(int k, int c) { bv[k] = 1; comp[k] = c; compVal[c] |= 1<<k; for (int i = 0; i < 30; i++) if (bitAdj[i][k] && !bitNo[i][k] && !bv[i]) dfs2(i, c); } int main() { scanf("%d%d", &N, &M); for (int i = 1, A, B, C; i <= M; i++) { scanf("%d%d%d", &A, &B, &C); adj[A].push_back({B, C, i}); adj[B].push_back({A, C, i}); } st.push_back(0); dfs(1, 0); D("vals = "); for (int i : vals) D("%d ", i); D("\n"); for (int i : vals) { for (int j = 0; j < 30; j++) if ((1<<j) & i) { bitVis[j] = 1; for (int k = 0; k < 30; k++) if (j != k) { if ((1<<k) & i) bitAdj[j][k] = bitAdj[k][j] = 1; else bitNo[j][k] = bitNo[k][j] = 1; } } } for (int i = 0; i < 5; i++) { for (int j = 0; j < 5; j++) D("%d ", bitAdj[i][j] && !bitNo[i][j]); D("\n"); } for (int i = 0; i < 30; i++) if (bitVis[i] && !bv[i]) dfs2(i, nc++); for (int i = 0; i < nc; i++) D("comp = %d val = %d\n", i, compVal[i]); for (int i = 1; i <= M; i++) if (visEdge[i]) for (int j = 0; j < 30; j++) if ((1<<j) & valEdge[i]) applyto[comp[j]].insert(i); D("ANS:\n\n"); printf("%d\n", nc); for (int i = 0; i < nc; i++) { printf("%d %d", compVal[i], applyto[i].size()); for (int j : applyto[i]) printf(" %d", j); printf("\n"); } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 54 ms | 6520 KB | Output is correct |
2 | Correct | 39 ms | 6520 KB | Output is correct |
3 | Correct | 13 ms | 3576 KB | Output is correct |
4 | Correct | 11 ms | 3576 KB | Output is correct |
5 | Correct | 90 ms | 9920 KB | Output is correct |
6 | Correct | 86 ms | 9160 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 20 ms | 4472 KB | Output is correct |
2 | Correct | 19 ms | 4188 KB | Output is correct |
3 | Correct | 24 ms | 4860 KB | Output is correct |
4 | Correct | 32 ms | 5272 KB | Output is correct |
5 | Correct | 114 ms | 9976 KB | Output is correct |
6 | Correct | 58 ms | 7032 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 119 ms | 12700 KB | Too many operations |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 96 ms | 11256 KB | Too many operations |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 102 ms | 13688 KB | Too many operations |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 320 ms | 31040 KB | Too many operations |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 171 ms | 14920 KB | Too many operations |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 445 ms | 31740 KB | Too many operations |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 32 ms | 5624 KB | Too many operations |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 248 ms | 17624 KB | Too many operations |
2 | Halted | 0 ms | 0 KB | - |