# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
151280 | Ruxandra985 | Teoretičar (COCI18_teoreticar) | C++14 | 12077 ms | 25468 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
/// o sa incerc asta dar nu cred ca e ok pt ca chiar daca ipotetic
/// intuitia mea ar fi corecta , nu sunt 100% sigura ca 12 secunde imi ajung:p
#include <cstdio>
#include <vector>
#include <algorithm>
#include <bitset>
using namespace std;
vector <pair <int,int> > v[200010];
int sol[500010];
int r[200001];
pair <int,int> l[200001];
bitset <200010> f;
int cuplez (int nod){
int i,vecin;
if (f[nod])
return 0;
f[nod]=1;
for (i=0;i<v[nod].size();i++){
vecin=v[nod][i].first;
if (!r[vecin] && !sol[v[nod][i].second]){ /// il cuplez direct
l[nod].first=vecin;
l[nod].second = v[nod][i].second;
r[vecin]=nod;
return 1;
}
}
f[nod]=1;
/// altfel, caut alta modalitate
for (i=0;i<v[nod].size();i++){
vecin=v[nod][i].first;
if (!sol[v[nod][i].second] && cuplez (r[vecin])){ /// il pot cupla pe nod cu vecin
l[nod]=make_pair(vecin , v[nod][i].second);
r[vecin]=nod;
return 1;
}
}
return 0;
}
int main()
{
FILE *fin = stdin;
FILE *fout = stdout;
int st,dr,m,i,x,y,left,cul,ok;
fscanf (fin,"%d%d%d",&st,&dr,&m);
for (i=1;i<=m;i++){
fscanf (fin,"%d%d",&x,&y);
v[x].push_back(make_pair(y,i));
}
left = m;
cul = 0;
while (left){ /// gasesti cuplaj maxim si elimini muchiile din el
cul++;
do{
ok=0;
f.reset();
for (i=1;i<=st;i++){
if (!l[i].first)
ok=(ok|cuplez(i));
}
}
while (ok==1);
for (i=1;i<=st;i++){
if (l[i].first){
r[l[i].first] = 0;
left--;
sol[l[i].second] = cul; /// scoti muchia asta
}
l[i] = make_pair(0,0);
}
}
fprintf (fout,"%d\n",cul);
for (i=1;i<=m;i++)
fprintf (fout,"%d\n",sol[i]);
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |