# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
858375 | 2023-10-08T09:22:13 Z | jamkel | Teoretičar (COCI18_teoreticar) | C++14 | 12000 ms | 56060 KB |
#include <bits/stdc++.h> using namespace std; #define st first #define nd second typedef long long ll; int wynik=0; bool dfs(vector<vector<pair<int,int>>>&a,vector<vector<pair<int,int>>>&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==wynik) { if(dfs(a,b,odwiedzone,false,b[co][i].st)) { b[co][i].nd=-1; 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=-1; break; } } return true; } return false; } } return true; } else { for(int i=0;i<a[co].size();i++) { if(a[co][i].nd==-1) { if(dfs(a,b,odwiedzone,true,a[co][i].st)) { a[co][i].nd=wynik; 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=wynik; 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<pair<int,int>>e(m); vector<vector<pair<int,int>>>a(l); vector<vector<pair<int,int>>>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; x--; y--; a[x].push_back({y,-1}); b[y].push_back({x,-1}); e[i]={x,y}; } int ile=0; while(ile<m) { bool ok=true; vector<bool>w(l); 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; } } } } wynik++; } map<pair<int,int>,int>ma; for(int i=0;i<a.size();i++) { for(int j=0;j<a[i].size();j++) { ma[{i,a[i][j].st}]=a[i][j].nd+1; } } cout<<wynik<<endl; for(int i=0;i<m;i++) { cout<<ma[e[i]]<<endl; } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 344 KB | Output is correct |
2 | Correct | 1 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 0 ms | 600 KB | Output is correct |
5 | Correct | 1 ms | 348 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 348 KB | Output is correct |
2 | Correct | 1 ms | 460 KB | Output is correct |
3 | Correct | 1 ms | 500 KB | Output is correct |
4 | Correct | 1 ms | 348 KB | Output is correct |
5 | Correct | 0 ms | 348 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 9 ms | 1112 KB | too many colors |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 9 ms | 856 KB | Output is correct |
2 | Correct | 11 ms | 1112 KB | Output is correct |
3 | Correct | 11 ms | 1116 KB | Output is correct |
4 | Incorrect | 8 ms | 860 KB | too many colors |
5 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1775 ms | 46400 KB | too many colors |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 2286 ms | 47964 KB | too many colors |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 11229 ms | 56060 KB | Output is correct |
2 | Execution timed out | 12102 ms | 38044 KB | Time limit exceeded |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6199 ms | 52144 KB | Output is correct |
2 | Execution timed out | 12087 ms | 38228 KB | Time limit exceeded |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 12016 ms | 41052 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1588 ms | 41044 KB | Output is correct |
2 | Execution timed out | 12085 ms | 36476 KB | Time limit exceeded |
3 | Halted | 0 ms | 0 KB | - |