Submission #908618

#TimeUsernameProblemLanguageResultExecution timeMemory
908618lightonPaint (COI20_paint)C++17
0 / 100
61 ms51908 KiB
#include<bits/stdc++.h> #define forf(i,a,b) for(int i = a; i<=b; i++) #define all(v) v.begin(),v.end() typedef long long ll; using namespace std; int R,S,N,Q; vector<vector<int> > num, col; struct DSU{ int grp[200011]; int col[200011]; vector<int> comp[200011]; vector<int> adj[200011]; void init(){ forf(i,1,N){ grp[i] = i; comp[i].push_back(i); } } int f(int x){ if(grp[x] == x) return x; return grp[x] = f(grp[x]); } void u(int x, int y){ x = f(x); y=f(y); if(adj[x].size() > adj[y].size()) swap(x,y); for(int i : adj[x]) adj[y].push_back(i); grp[x] = y; } void merg(int x){ for(int i : adj[x]){ if(f(i) == f(x)) continue; if(col[f(i)] == col[f(x)]) u(x,i); } } } dsu; void setdsu(){ forf(i,1,R){ forf(j,1,S){ dsu.col[num[i][j]] = col[i][j]; } } forf(i,1,R-1){ forf(j,1,S){ dsu.adj[num[i][j]].push_back(num[i+1][j]); dsu.adj[num[i+1][j]].push_back(num[1][j]); } } forf(i,1,R){ forf(j,1,S-1){ dsu.adj[num[i][j+1]].push_back(num[i][j]); dsu.adj[num[i][j]].push_back(num[1][j+1]); } } } int main(){ scanf("%d %d" , &R,&S); N=R*S; num.resize(R+2); col.resize(R+2); forf(i,0,R+1){num[i] = vector<int>(S+2,-1); col[i] = vector<int>(S+2,-1);} dsu.init(); forf(i,1,R){ forf(j,1,S){ scanf("%d" , &col[i][j]); num[i][j] = S*(i-1)+j; } } setdsu(); forf(i,1,R){ forf(j,1,S){ dsu.merg(num[i][j]); } } scanf("%d" , &Q); while(Q--){ int x,y,c; scanf("%d %d %d" , &x,&y,&c); dsu.col[dsu.f(num[x][y])]=c; dsu.merg(num[x][y]); } forf(i,1,R) { forf(j, 1, S) printf("%d" , dsu.col[dsu.f(num[i][j])]); printf("\n"); } }

Compilation message (stderr)

paint.cpp: In function 'int main()':
paint.cpp:59:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |     scanf("%d %d" , &R,&S);
      |     ~~~~~^~~~~~~~~~~~~~~~~
paint.cpp:67:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |             scanf("%d" , &col[i][j]);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~
paint.cpp:79:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |     scanf("%d" , &Q);
      |     ~~~~~^~~~~~~~~~~
paint.cpp:82:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |         scanf("%d %d %d" , &x,&y,&c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...