Submission #92096

#	Time	Username	Problem	Language	Result	Execution time	Memory
92096		Kastanda	Praktični (COCI18_prakticni)	C++11	130 / 130	142 ms	15912 KiB

parkticni

#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 (stderr)

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 / 13
• Subtask 2: 13 / 13
• Subtask 3: 13 / 13
• Subtask 4: 13 / 13
• Subtask 5: 13 / 13
• Subtask 6: 13 / 13
• Subtask 7: 13 / 13
• Subtask 8: 13 / 13
• Subtask 9: 13 / 13
• Subtask 10: 13 / 13