Submission #1206433

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206433		tgirolami09	Praktični (COCI18_prakticni)	C++20	0 / 130	48 ms	14508 KiB

parkticni

#pragma GCC optimize("O2,unroll-loops")

#include <iostream>
#include <vector>


using namespace std;

const int maxN = 100001;

struct path{
    int to;
    int idx;
};

vector<int> pathWeights;

vector<vector<path> > graph(maxN,vector<path>());

//Depth at which it was visited 0 if never
vector<int> visited(maxN,false);

vector<int> xorContinued = {0};

vector<vector<int> > toFlip(32,vector<int>());

//For st-1
int st1Flip = 0;
int st1PathIdx = 0;

int dfs(int currPos, int parent, int depth, int pathId){
    //When cycle detection then do my shenanigans with the XOR vector
    //Then add to a list that for every bit to xor with contains a list of edges to XOR with

    if (visited[currPos]!=0){
        // printf("Detected cycle\n");
        // printf("Xor continued : ");
        // for (int i : xorContinued){
            // printf("%d, ",i);
        // }
        // printf("\n");
        //Cycle logic here

        //Get all bits that need to be flipped
        int startIdx = visited[currPos];
        int endIdx = depth;

        int beforeStartVal = xorContinued[startIdx];
        int lastVal = xorContinued[endIdx];

        int bitsToFlip = beforeStartVal ^ lastVal; //Remove bits that are wrongly flipped outside of loop
        if (bitsToFlip!=0){
            st1Flip = bitsToFlip;
            st1PathIdx = pathId;
        }

        //For each bit to flip we need to add the segment to a list for that bit
        // printf("Bits to flip : ");
        for (int i = 0;i<31;++i){
            if ((bitsToFlip & (1<<i)) != 0){
                //Bit is set
                toFlip[i].push_back(pathId);
                // printf("1");
            }
            else{
                // printf("0");
            }
        }
        // printf("\n");

        //Should I change this segments value ? (Yes)
        return bitsToFlip;
    }

    visited[currPos] = depth;

    for (int i = 0;i<graph[currPos].size();++i){
        path p = graph[currPos][i];
        // printf("Visiting %d child of %d\n",p.to,currPos);
        if (p.to != parent){
            int lastXor = xorContinued[depth]; //Last value in xorContinued
            int weight = pathWeights[p.idx-1];
            xorContinued.push_back(lastXor ^ weight);
            int toFlip = dfs(p.to,currPos,depth+1,p.idx);
            if (toFlip!=-1){
                // printf("Changing path %d's weight from %d to %d\n",p.idx,weight,weight^toFlip);
                pathWeights[p.idx-1] = (weight ^ toFlip);
            }
            xorContinued.pop_back();
        }
    }

    // visited[currPos] = 0;
    return -1;
}


//only doing for subtask 1
int main(){
    int nbNodes;
    int nbPaths;
    scanf("%d %d",&nbNodes,&nbPaths);

    for (int i = 0;i<nbPaths;++i){
        int from, to, weight;
        scanf("%d %d %d",&from, &to, &weight);
        pathWeights.push_back(weight);
        graph[from].push_back({to,i+1});
        graph[to].push_back({from,i+1});
    }

    dfs(1,0,0,0);

    //Not great but i'm tired
    int nbFlipping = 0;
    for (int i = 0;i<31;++i){
        if (!toFlip[i].empty()){
            ++nbFlipping;
        }
    }
    printf("%d\n",nbFlipping);

    if (nbFlipping==0){
        return 0;
    }

    else {
        printf("%d 1 %d\n",st1Flip,st1PathIdx);
    }

    // else{
    //     for (int i = 0;i<31;++i){
    //         if (!toFlip[i].empty()){
    //             printf("%d ",(1<<i));
    //             printf("%d ",(int)toFlip[i].size());
    //             for (int j = 0;j<toFlip[i].size();++j){
    //                 printf("%d ",toFlip[i][j]);
    //             }
    //             printf("\n");
    //         }
    //     }
    // }
}

Compilation message (stderr)

parkticni.cpp: In function 'int main()':
parkticni.cpp:102:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |     scanf("%d %d",&nbNodes,&nbPaths);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
parkticni.cpp:106:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |         scanf("%d %d %d",&from, &to, &weight);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 13
• Subtask 2: 0 / 13
• Subtask 3: 0 / 13
• Subtask 4: 0 / 13
• Subtask 5: 0 / 13
• Subtask 6: 0 / 13
• Subtask 7: 0 / 13
• Subtask 8: 0 / 13
• Subtask 9: 0 / 13
• Subtask 10: 0 / 13