Submission #1206418

#TimeUsernameProblemLanguageResultExecution timeMemory
1206418tgirolami09Praktični (COCI18_prakticni)C++20
0 / 130
1097 ms11496 KiB
#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:99:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |     scanf("%d %d",&nbNodes,&nbPaths);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
parkticni.cpp:103:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |         scanf("%d %d %d",&from, &to, &weight);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...