제출 #151576

#제출 시각아이디문제언어결과실행 시간메모리
151576Ruxandra985Teoretičar (COCI18_teoreticar)C++14
91 / 130
12090 ms73692 KiB
#include <cstdio> #include <vector> #include <algorithm> using namespace std; vector <pair <int,int> > v[400010]; vector <int > mc; pair <int,int> init[500010]; int sol[500010]; int g[400010]; int prv[400010]; int f[500010]; int m , st , dr; void dfs (int nod,int pus,vector <int> other[2]){ int vecin,mch; for (int i = prv[nod] ; i <v[nod].size();i++){ prv[nod] = i; vecin = v[nod][prv[nod]].first; mch = v[nod][prv[nod]].second; if (!f[mch]){ f[mch] = 1; g[nod]--; g[vecin]--; other[pus].push_back(mch); prv[nod]++; dfs (vecin,1-pus,other); return; } prv[nod]++; } } void pune (vector <int> mc , int &cul){ /// pt chestia cu 2^x , o sa imparti muchiile mereu in 2 int i,x,y,idx,gmax; /// verifici daca setul tau e independent gmax = 0; for (i=0;i<mc.size();i++){ x = init[mc[i]].first; y = init[mc[i]].second; prv[x] = prv[y] = 0; idx = mc[i]; f[idx] = 0; v[x].push_back(make_pair(y,idx)); v[y].push_back(make_pair(x,idx)); g[y]++; g[x]++; gmax = max (gmax , g[x]); gmax = max (gmax , g[y]); } if ( gmax < 2 ) { /// e independent , pui cul peste tot if (!mc.empty()) cul++; for (i=0;i<mc.size();i++){ idx = mc[i]; g[init[mc[i]].first] = g[init[mc[i]].second] = 0; v[init[mc[i]].first].clear(); v[init[mc[i]].second].clear(); sol[idx] = cul; } return; } vector <int> other[2]; /// vrei sa imparti muchiile in doua seturi astfel incat niciuna din primul set /// sa nu aiba aceeasi culoare cu una din al doilea set /// iei pur si simplu drumuri maximale si pui muchiile alternant,cum faceam /// si la euler /// trebuie sa am grija ca mereu sa pun ceva in ambele other uri for (i=1;i<=st+dr;i++){ if (g[i]%2) dfs(i,0,other); } for (i=1;i<=st+dr;i++){ while (g[i]){ dfs (i,0,other); } v[i].clear(); } pune(other[0],cul); pune(other[1],cul); } char buff[7000000]; int poz = 0; int getnr(){ int nr = 0; while ('0' > buff[poz] || buff[poz] > '9') poz++; while ('0'<=buff[poz] && buff[poz]<='9'){ nr = nr * 10 + buff[poz] - '0'; poz++; } return nr; } int main() { FILE *fin = stdin; FILE *fout = stdout; int i,x,y,cul=0; fread (buff,1,7000000,fin); st = getnr(); dr = getnr(); m = getnr(); int mi = m; for (i=1;i<=m;i++){ x = getnr(); y = getnr(); y+=st; init[i] = make_pair(x,y); mc.push_back(i); } cul = 0; pune(mc,cul); fprintf (fout,"%d\n",cul); for (i=1;i<=mi;i++) fprintf (fout,"%d\n",sol[i]); return 0; }

컴파일 시 표준 에러 (stderr) 메시지

teoreticar.cpp: In function 'void dfs(int, int, std::vector<int>*)':
teoreticar.cpp:15:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = prv[nod] ; i <v[nod].size();i++){
                             ~~^~~~~~~~~~~~~~
teoreticar.cpp: In function 'void pune(std::vector<int>, int&)':
teoreticar.cpp:36:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<mc.size();i++){
              ~^~~~~~~~~~
teoreticar.cpp:52:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i=0;i<mc.size();i++){
                  ~^~~~~~~~~~
teoreticar.cpp: In function 'int main()':
teoreticar.cpp:100:11: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     fread (buff,1,7000000,fin);
     ~~~~~~^~~~~~~~~~~~~~~~~~~~
#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...