oj.uz

Submission #92096

# Submission time Handle Problem Language Result Execution time Memory
92096 2019-01-01T14:14:08 Z Kastanda Praktični (COCI18_prakticni) C++11
130 / 130
 142 ms 15912 KB 
#include<bits/stdc++.h>
using namespace std;
const int N = 100005;
int n, m, A[N], F[N], T[N], W[N], MR[N];
vector < int > E, P, Adj[N], Q[40];
void DFS(int v, int p)
{
    MR[v] = 1;
    for (int &id : Adj[v])
        if (id != p)
        {
            int u = T[id] ^ F[id] ^ v;
            if (MR[u] == 1 && ((A[v] ^ A[u]) != W[id]))
            {
                E.push_back(id);
                P.push_back(A[v] ^ A[u] ^ W[id]);
            }
            if (MR[u] == 0)
                A[u] = A[v] ^ W[id], DFS(u, id);
        }
    MR[v] = 2;
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++)
    {
        scanf("%d%d%d", &F[i], &T[i], &W[i]);
        Adj[F[i]].push_back(i);
        Adj[T[i]].push_back(i);
    }
    DFS(1, -1);
    int r = 0;
    for (int i = 30; ~i; i--)
    {
        for (int j = r; j < P.size(); j++)
            if (P[j] & (1 << i))
                {swap(P[r], P[j]); break;}
        if (r < P.size() && (P[r] & (1 << i)))
        {
            for (int j = 0; j < P.size(); j++)
                if (j != r && (P[j] & (1 << i)))
                    P[j] ^= P[r];
            r ++;
        }
    }
    P.resize(r);
    for (int &id : E)
    {
        int t = A[F[id]] ^ A[T[id]] ^ W[id];
        for (int i = 0; i < r; i++)
        {
            int bit = 31 - __builtin_clz(P[i]);
            if ((t >> bit) & 1)
                t ^= P[i], Q[i].push_back(id);
        }
    }
    printf("%d\n", r);
    for (int i = 0; i < r; i++)
    {
        printf("%d %d", P[i], (int)Q[i].size());
        for (int &id : Q[i])
            printf(" %d", id);
        printf("\n");
    }
    return (0);
}

Compilation message

parkticni.cpp: In function 'int main()':
parkticni.cpp:36:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = r; j < P.size(); j++)
                         ~~^~~~~~~~~~
parkticni.cpp:39:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (r < P.size() && (P[r] & (1 << i)))
             ~~^~~~~~~~~~
parkticni.cpp:41:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int j = 0; j < P.size(); j++)
                             ~~^~~~~~~~~~
parkticni.cpp:25:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~
parkticni.cpp:28:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", &F[i], &T[i], &W[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 6520 KB Output is correct
2 Correct 36 ms 7008 KB Output is correct
3 Correct 10 ms 3576 KB Output is correct
4 Correct 11 ms 3832 KB Output is correct
5 Correct 84 ms 12408 KB Output is correct
6 Correct 77 ms 11000 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 4344 KB Output is correct
2 Correct 17 ms 4344 KB Output is correct
3 Correct 22 ms 5240 KB Output is correct
4 Correct 29 ms 5708 KB Output is correct
5 Correct 74 ms 9976 KB Output is correct
6 Correct 45 ms 7160 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 7672 KB Output is correct
2 Correct 76 ms 9020 KB Output is correct
3 Correct 4 ms 2628 KB Output is correct

Subtask #4
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 9848 KB Output is correct
2 Correct 135 ms 14452 KB Output is correct
3 Correct 5 ms 2808 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 8696 KB Output is correct
2 Correct 87 ms 8716 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 10796 KB Output is correct
2 Correct 46 ms 6648 KB Output is correct

Subtask #7
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 10104 KB Output is correct
2 Correct 95 ms 12888 KB Output is correct
3 Correct 88 ms 8952 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 13944 KB Output is correct
2 Correct 142 ms 15912 KB Output is correct
3 Correct 132 ms 15652 KB Output is correct

Subtask #9
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 5240 KB Output is correct
2 Correct 34 ms 5944 KB Output is correct
3 Correct 97 ms 11100 KB Output is correct

Subtask #10
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 11128 KB Output is correct
2 Correct 56 ms 7440 KB Output is correct
3 Correct 141 ms 14864 KB Output is correct