Submission #414494

#TimeUsernameProblemLanguageResultExecution timeMemory
414494Ruxandra985Joker (BOI20_joker)C++14
14 / 100
2049 ms14248 KiB
#include <bits/stdc++.h> #define DIMN 400010 using namespace std; int tt[DIMN]; int sz[DIMN] , opt[DIMN]; int n , m; pair <int , int> mch[DIMN]; vector <pair <int , int> > s; vector <int> v; int idk = 76; int root (int x){ while (tt[x] != x) x = tt[x]; return x; } void unite (int x, int y){ int radx = root(x), rady = root(y); //printf ("add %d %d\n" , x , y); if (sz[radx] < sz[rady]) swap (radx,rady); s.push_back(make_pair(radx,rady)); /// stiva pt undo sz[radx] += sz[rady]; tt[rady] = radx; } void undo (){ int x = s.back().first, y = s.back().second; s.pop_back(); //printf ("undo\n"); sz[x] -= sz[y]; tt[y] = y; } void solve (int st , int dr , int l , int r){ int mid = (st + dr)/2 , i , poz , x , y , m2; /*if (st == 77 && dr == 90){ printf ("a"); } if (st == 63 && dr == 64){ printf ("%d %d %d %d\n" , st , dr , l , r); for (i = 0 ; i < v.size() ; i++){ printf ("%d " , v[i]); } printf ("\n\n\n\n"); printf ("a"); }*/ /*if (st <= 82 && 82 <= dr){ printf ("%d %d %d %d\n" , st , dr , l , r); for (i = 0 ; i < v.size() ; i++){ printf ("%d " , v[i]); } printf ("\n\n\n\n"); }*/ for (i = dr ; i >= mid ; i--){ x = mch[i].first; y = mch[i].second; unite (x , y + n); unite (y , x + n); v.push_back(i); } l = max(l , 1); poz = 0; for (i = l ; i <= r && i < mid ; i++){ x = mch[i].first; y = mch[i].second; if (root(x) == root(y) || root(y + n) == root(x + n)){ break; } unite (x , y + n); unite (y , x + n); v.push_back(i); poz = i; } opt[mid] = poz; for (i = l ; i <= poz ; i++){ undo(); undo(); v.pop_back(); } if (st <= mid - 1) solve (st , mid - 1 , l , poz); for (i = mid ; i <= dr; i++){ undo(); undo(); v.pop_back(); } if (mid + 1 <= dr){ m2 = (dr + mid + 1) / 2; for (i = l ; i < poz ; i++){ x = mch[i].first; y = mch[i].second; unite (x , y + n); unite (y , x + n); v.push_back(i); } solve(mid + 1 , dr , poz , r); for (i = l ; i < poz ; i++){ undo(); undo(); v.pop_back(); } } /// convine sa te duci mai intai in dreapta, pastrezi tot ce ai adaugat } int main() { FILE *fin = stdin; FILE *fout = stdout; int q , i , x , y , poz , j , l , r; fscanf (fin,"%d%d%d",&n,&m,&q); for (i = 1 ; i <= m ; i++){ fscanf (fin,"%d%d",&mch[i].first,&mch[i].second); } /// opt se calculeaza intre 1 si M + 1 for (i = 1 ; i <= 2 * n ; i++){ tt[i] = i; sz[i] = 1; } /*/// ---------------------------------------------------------------------- for (i = m ; i >= idk ; i--){ x = mch[i].first; y = mch[i].second; if (root(x) == root(y) || root(y + n) == root(x + n)){ break; } unite (x , y + n); unite (y , x + n); } for (i = 1 ; i < idk ; i++){ x = mch[i].first; y = mch[i].second; if (root(x) == root(y) || root(y + n) == root(x + n)){ break; } unite (x , y + n); unite (y , x + n); } printf ("%d\n" , i - 1); for (i = 1 ; i <= 2 * n ; i++){ tt[i] = i; sz[i] = 1; } s.clear(); /// ----------------------------------------------------------------------*/ for (i = m ; i ; i--){ x = mch[i].first; y = mch[i].second; if (root(x) == root(y) || root(y + n) == root(x + n)){ break; } unite (x , y + n); unite (y , x + n); } poz = i + 1; for (j = i + 1 ; j <= m ; j++){ undo(); undo(); } int where = poz; solve (poz , m , 1 , m); /// te asiguri ca dreapta nu cauzeaza ciclu impar //printf ("-----------------\n"); for (i = 1 ; i <= m ; i++){ x = mch[i].first; y = mch[i].second; if (root(x) == root(y) || root(y + n) == root(x + n)){ break; } unite (x , y + n); unite (y , x + n); } poz = i - 1; opt[m + 1] = poz; for (j = i - 1 ; j ; j--){ undo(); undo(); } for (;q;q--){ fscanf (fin,"%d%d",&l,&r); if (opt[r + 1] >= l - 1 && r + 1 >= where) fprintf (fout,"NO\n"); else fprintf (fout,"YES\n"); } return 0; }

Compilation message (stderr)

Joker.cpp: In function 'void solve(int, int, int, int)':
Joker.cpp:43:47: warning: variable 'm2' set but not used [-Wunused-but-set-variable]
   43 |     int mid = (st + dr)/2 , i , poz , x , y , m2;
      |                                               ^~
Joker.cpp: In function 'int main()':
Joker.cpp:151:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  151 |     fscanf (fin,"%d%d%d",&n,&m,&q);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
Joker.cpp:153:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  153 |         fscanf (fin,"%d%d",&mch[i].first,&mch[i].second);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Joker.cpp:251:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  251 |         fscanf (fin,"%d%d",&l,&r);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~
#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...