제출 #225517

#제출 시각아이디문제언어결과실행 시간메모리
225517nicolaalexandraColors (RMI18_colors)C++14
78 / 100
3065 ms64480 KiB
#include <bits/stdc++.h> #define DIM 150010 #define DIMBUFF 10000000 #define INF 2000000000 using namespace std; vector <int> poz_a[DIM],poz_b[DIM]; int a[DIM],b[DIM],f[DIM],f2[DIM],c[DIM]; int mrk[DIM],fth[DIM],Size[DIM]; int t,n,m,i,j,x,y,k,sol,mini,maxi,ok,g,sol_final,u,pos; char buff[DIMBUFF]; vector <pair<int,int> > aint2[DIM*4]; pair<int,int> s[DIM]; void update_aint (int nod, int st, int dr, int x, int y, int a, int b){ if (x <= st && dr <= y){ aint2[nod].push_back(make_pair(a,b)); return; } int mid = (st+dr)>>1; if (x <= mid) update_aint(nod<<1,st,mid,x,y,a,b); if (y > mid) update_aint ((nod<<1)|1,mid+1,dr,x,y,a,b); } int get_rad (int x){ while (x != fth[x]) x = fth[x]; return x; } void unite (int radx, int rady){ if (radx == rady) return; if (Size[radx] < Size[rady]); swap (radx,rady); /// tin minte o stiva cu update urile pe care le fac ca sa pot sa fac undo s[++u] = make_pair(radx,rady); Size[radx] += Size[rady]; fth[rady] = radx; } void undo (){ int x = s[u].first, y = s[u].second; u--; Size[x] -= Size[y]; fth[y] = y; } void query_aint (int nod, int st, int dr){ /// am intrat prima oara in nod, trb sa adaug muchiile if (!sol_final) return; int size_init = u; /// ca sa stiu dupa cate undo uri trb sa fac for (int i=0;i<aint2[nod].size();++i){ int radx = get_rad (aint2[nod][i].first), rady = get_rad (aint2[nod][i].second); unite (radx,rady); } if (st == dr){ /// acum trb sa fac query ul /// marchez culorile de a for (int i=0;i<poz_a[st].size();++i){ int x = get_rad(poz_a[st][i]); mrk[x] = st; } for (int i=0;i<poz_b[st].size();++i){ int x = get_rad(poz_b[st][i]); if (mrk[x] != st){ sol_final = 0; break; } } } else { int mid = (st+dr)>>1; query_aint(nod<<1,st,mid); query_aint((nod<<1)|1,mid+1,dr); } /// am terminat cu nod, trb sa dau undo while (u > size_init) undo(); } int get_nr(){ while (!(buff[pos] >= '0' && buff[pos] <= '9')) pos++; int nr = 0; while (buff[pos] >= '0' && buff[pos] <= '9'){ nr = nr*10 + buff[pos] - '0'; pos++; } return nr; } int main (){ // FILE *fin = fopen ("colors2.in","r"); // FILE *fout = fopen ("colors2.out","w"); FILE *fin = stdin; FILE *fout = stdout; fread (buff,1,DIMBUFF,fin); t = get_nr(); for (int q=1;q<=t;++q){ //if (q == 36) // q = 36; //cin>>n>>m; n = get_nr(), m = get_nr(); for (i=1;i<=n;++i){ //L[i].clear(); poz_a[i].clear(); poz_b[i].clear(); f[i] = mrk[i] = 0; Size[i] = 1; fth[i] = i; } for (i=1;i<=4*n;++i) aint2[i].clear(); for (i=1;i<=n;++i){ //cin>>a[i]; a[i] = get_nr(); ++f[a[i]]; poz_a[a[i]].push_back(i); } int ok = 1; for (i=1;i<=n;++i){ //cin>>b[i]; b[i] = get_nr(); poz_b[b[i]].push_back(i); if (b[i] > a[i] || !f[b[i]]) ok = 0; } for (i=1;i<=m;++i){ //cin>>x>>y; x = get_nr(), y = get_nr(); /// fac update in aint cu intervalul pt muchia asta int mini = min (a[x],a[y]); int maxi = max (b[x],b[y]); update_aint (1,1,n,maxi,mini,x,y); } if (!ok){ //cout<<0<<"\n"; fprintf(fout,"0\n"); continue; } if (n == 1 && !m){ if (a[1] == b[1]) fprintf(fout,"1\n"); else fprintf(fout,"0\n"); continue; } if (n == 2 && m == 1){ if ( (a[1] == b[1] && a[2] == b[2]) || (min (a[1],a[2]) == b[1] && min (a[1],a[2]) == b[2]) ) fprintf(fout,"1\n"); else fprintf(fout,"0\n"); continue; } /// de aici devine interesant sol_final = 1; //s.clear(); u = 0; query_aint (1,1,n); fprintf(fout,"%d\n",sol_final); //cout<<sol_final<<"\n"; } return 0; }

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

colors.cpp: In function 'void unite(int, int)':
colors.cpp:38:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
     if (Size[radx] < Size[rady]);
     ^~
colors.cpp:39:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
         swap (radx,rady);
         ^~~~
colors.cpp: In function 'void query_aint(int, int, int)':
colors.cpp:65:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<aint2[nod].size();++i){
                  ~^~~~~~~~~~~~~~~~~~
colors.cpp:73:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i=0;i<poz_a[st].size();++i){
                      ~^~~~~~~~~~~~~~~~~
colors.cpp:78:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i=0;i<poz_b[st].size();++i){
                      ~^~~~~~~~~~~~~~~~~
colors.cpp: In function 'int main()':
colors.cpp:112: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,DIMBUFF,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...