| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 858398 | jamkel | Teoretičar (COCI18_teoreticar) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define st first
#define nd second
typedef long long ll;
ll wynik=0;
bool dfs(vector<vector<pair<ll,ll>>>&a,vector<vector<pair<ll,ll>>>&b, vector<bool>&odwiedzone,bool czy,ll co)
{
ll f=0;
if(czy)
{
f+=a.size();
}
if(odwiedzone[co+f])
{
return false;
}
odwiedzone[co+f]=true;
if(czy)
{
for(ll 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(ll 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(ll 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(ll 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);
ll l,r,m;
cin>>l>>r>>m;
vector<pair<ll,ll>>e(m);
vector<vector<pair<ll,ll>>>a(l);
vector<vector<pair<ll,ll>>>b(r);
random_shuffle(q.begin(),q.end());
for(ll i=0;i<m;i++)
{
ll x,y;
cin>>x>>y;
x--;
y--;
a[x].push_back({y,-1});
b[y].push_back({x,-1});
e[i]={x,y};
}
ll ile=0;
while(ile<m)
{
bool ok=true;
vector<bool>w(l);
vector<ll>q(l);
srand((unsigned) time(NULL));
for(ll i=0;i<l;i++)
{
q[i]=i;
}
while(ok)
{
ok=false;
vector<bool>odwiedzone(l+r);
for(ll 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<ll,ll>,ll>ma;
for(ll i=0;i<a.size();i++)
{
for(ll j=0;j<a[i].size();j++)
{
ma[{i,a[i][j].st}]=a[i][j].nd+1;
}
}
cout<<wynik<<endl;
for(ll i=0;i<m;i++)
{
cout<<ma[e[i]]<<endl;
}
}