# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
858353 | 2023-10-08T08:28:55 Z | jamkel | Teoretičar (COCI18_teoreticar) | C++14 | 838 ms | 28604 KB |
#include <bits/stdc++.h> using namespace std; #define st first #define nd second typedef long long ll; bool dfs(vector<vector<pair<int,bool>>>&a,vector<vector<pair<int,bool>>>&b, vector<bool>&odwiedzone,bool czy,int co) { int f=0; if(czy) { f+=a.size(); } if(odwiedzone[co+f]) { return false; } odwiedzone[co+f]=true; if(czy) { for(int i=0;i<b[co].size();i++) { if(b[co][i].nd==true) { if(dfs(a,b,odwiedzone,false,b[co][i].st)) { b[co][i].nd=false; for(int o=0;o<a[b[co][i].st].size();o++) { if(a[b[co][i].st][o].st==co) { a[b[co][i].st][o].nd=false; break; } } return true; } return false; } } return true; } else { for(int i=0;i<a[co].size();i++) { if(a[co][i].nd==false) { if(dfs(a,b,odwiedzone,true,a[co][i].st)) { a[co][i].nd=true; for(int o=0;o<b[a[co][i].st].size();o++) { if(b[a[co][i].st][o].st==co) { b[a[co][i].st][o].nd=true; break; } } return true; } } }return false; } } int main() { ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); int l,r,m; cin>>l>>r>>m; vector<vector<pair<int,bool>>>a(l); vector<bool>w(l); vector<vector<pair<int,bool>>>b(r); vector<int>q(l); srand((unsigned) time(NULL)); for(int i=0;i<l;i++) { q[i]=i; } random_shuffle(q.begin(),q.end()); for(int i=0;i<m;i++) { int x,y; cin>>x>>y; a[x].push_back({y,false}); b[y].push_back({x,false}); } bool ok=true; int ile=0; while(ok) { ok=false; vector<bool>odwiedzone(l+r); for(int i=0;i<l;i++) { if(!w[q[i]]) { if(dfs(a,b,odwiedzone,false,q[i])) { ok=true; ile++; w[q[i]]=true; } } } } cout<<ile<<endl; for(int i=0;i<l;i++) { for(int o=0;o<a[i].size();o++) { if(a[i][o].nd==true) { cout<<i<<" "<<a[i][o].st<<endl; } } } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 1 ms | 348 KB | Execution killed with signal 11 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 1 ms | 604 KB | Execution killed with signal 11 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 2 ms | 1116 KB | Execution killed with signal 11 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 1 ms | 604 KB | Execution killed with signal 11 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 799 ms | 27704 KB | Integer 99965 violates the range [1, 99038] |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 838 ms | 28604 KB | Integer 99936 violates the range [1, 99056] |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 3 ms | 5212 KB | Execution killed with signal 11 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 1 ms | 600 KB | Execution killed with signal 11 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 1 ms | 600 KB | Execution killed with signal 11 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 1 ms | 604 KB | Execution killed with signal 11 |
2 | Halted | 0 ms | 0 KB | - |