Submission #151316

#TimeUsernameProblemLanguageResultExecution timeMemory
151316Ruxandra985Teoretičar (COCI18_teoreticar)C++14
13 / 130
12103 ms121396 KiB
/// 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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...