# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
788947 | 2023-07-20T18:07:43 Z | YassirSalama | Simurgh (IOI17_simurgh) | C++14 | 1 ms | 212 KB |
#include "simurgh.h" #include<bits/stdc++.h> using namespace std; #define ll long long #define all(v) v.begin(),v.end() #define F first #define S second #define OVL(v,s) for(auto x:s) cout<<x<<s;cout<<endl; const int MAXN=10; vector<int> ans; vector<pair<int,int>> edges; vector<int> par(MAXN+100,0); int find(int node){ if(node==par[node]) return node; return par[node]=find(par[node]); } void make_set(){ for(int i=0;i<MAXN+100;i++) par[i]=i; } int N,M; bool search(int i){ if(i==edges.size()) { if(ans.size()==N-1){ if(count_common_roads(ans)==N-1) { // for(auto x:ans) cout<<x<<endl; return true; } return false; } else return false; } pair<int,int> p=edges[i]; int a=p.F,b=p.S; int A=find(a); int B=find(b); if(search(i+1)) return true;//without adding that edge else if(A!=B){ //here if we add that edge connect a o b then add the edge o ila makanch ndeconnectiwhum //heere nakhdu edge i njrbu bih sinon manakhduhch //atkun 2^n possibilité cause take or not take par[B]=A; ans.push_back(i); bool c=search(i+1); par[B]=B; if(c) return true; ans.pop_back(); // return false; } return false; } vector<int> find_roads(int n, vector<int> u, vector<int> c) { M=u.size(); N=n; make_set(); ans=vector<int>(0); for(int i=0;i<M;i++){ edges.push_back({u[i],c[i]}); } search(0); return ans; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 212 KB | WA in grader: NO |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 212 KB | WA in grader: NO |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 212 KB | WA in grader: NO |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 212 KB | correct |
2 | Incorrect | 0 ms | 212 KB | WA in grader: NO |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 212 KB | WA in grader: NO |
2 | Halted | 0 ms | 0 KB | - |