This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/// 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[400010],w[400010];
int sol[500010];
int ciclu[800001];
int g[400010];
int q[800010];
int f[500010];
bitset <200010> fq;
int main()
{
FILE *fin = stdin;
FILE *fout = stdout;
int st,dr,m,i,x,y,cul=0,elem,nod,vecin,c=0,j,mch,curr;
fscanf (fin,"%d%d%d",&st,&dr,&m);
int mi = m;
for (i=1;i<=m;i++){
fscanf (fin,"%d%d",&x,&y);
y+=st;
v[x].push_back(make_pair(y,i));
v[y].push_back(make_pair(x,i));
w[x].push_back(make_pair(y,i));
w[y].push_back(make_pair(x,i));
g[y]++; g[x]++;
}
for (i=1;i<=st+dr;i++){
if (g[i]%2 == 1){
v[0].push_back(make_pair(i,++m));
v[i].push_back(make_pair(0,m));
g[0]++; g[i]++;
}
v[0].push_back(make_pair(i,++m));
v[i].push_back(make_pair(0,m));
g[0]++; g[i]++;
v[0].push_back(make_pair(i,++m));
v[i].push_back(make_pair(0,m));
g[0]++; g[i]++;
}
/// formeaza un lant eulerian
q[1]=0;
elem=1;
while (elem){
nod=q[elem];
if (g[nod]==0){
// am luat toate muchiile care au legatura cu el, il afisez
ciclu[++c] = nod;
elem--;
continue;
}
while (v[nod].size() && f[v[nod].back().second]==1)
v[nod].pop_back();
vecin=v[nod].back().first;
g[nod]--;
g[vecin]--; // elimin muchia nod->vecin
f[v[nod].back().second]=1;
v[nod].pop_back();
q[++elem]=vecin;
}
for (i=1;i<c;i++){
if (!ciclu[i] || !ciclu[i+1])
continue;
x = ciclu[i];
y = ciclu[i+1];
if ( x > y ) /// x e mereu in left
swap(x,y);
fq.reset();
for (j=0;j<w[x].size();j++){
vecin = w[x][j].first;
mch = w[x][j].second;
if (y == vecin)
curr = mch;
else fq[sol[mch]] = 1;
}
for (j=0;j<w[y].size();j++){
vecin = w[y][j].first;
mch = w[y][j].second;
if (x == vecin)
curr = mch;
else fq[sol[mch]] = 1;
}
for (j=1;;j++){
if (!fq[j]){
sol[curr] = j;
cul = max (cul , j);
break;
}
}
}
fprintf (fout,"%d\n",cul);
for (i=1;i<=mi;i++)
fprintf (fout,"%d\n",sol[i]);
return 0;
}
Compilation message (stderr)
teoreticar.cpp: In function 'int main()':
teoreticar.cpp:74:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (j=0;j<w[x].size();j++){
~^~~~~~~~~~~~
teoreticar.cpp:81:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (j=0;j<w[y].size();j++){
~^~~~~~~~~~~~
teoreticar.cpp:20:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
fscanf (fin,"%d%d%d",&st,&dr,&m);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
teoreticar.cpp:23:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
fscanf (fin,"%d%d",&x,&y);
~~~~~~~^~~~~~~~~~~~~~~~~~
teoreticar.cpp:90:27: warning: 'curr' may be used uninitialized in this function [-Wmaybe-uninitialized]
sol[curr] = j;
~~~~~~~~~~^~~
# | 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... |