oj.uz

Submission #341913

# Submission time Handle Problem Language Result Execution time Memory
341913 2020-12-31T13:03:38 Z Hazem Paint (COI20_paint) C++14
8 / 100
 3000 ms 3308 KB 
/*
ID: tmhazem1
LANG: C++14
TASK: pprime
*/

#include <bits/stdc++.h>
using namespace std;

#define S second
#define F first
#define LL long long

const int N = 2e5 + 10;


LL LINF = 100000000000000000;
LL INF = 1000000000;
int MOD = 1e9+7;

vector<vector<int>>vec;
vector<vector<int>>component;
int colors[N];
int n,m;

int x[] = {1,-1,0,0};
int y[] = {0,0,1,-1};

bool in(int i,int j){

    return i>=0&&j>=0&&i<n&&j<m;
}

void dfs(int i,int j,int cnt){

    if(component[i][j]!=-1)return;
    component[i][j] = cnt;
    
    for(int k=0;k<4;k++){
        int i1 = i+x[k],j1 = j+y[k];
        if(in(i1,j1)&&vec[i][j]==vec[i1][j1])
            dfs(i1,j1,cnt);
    }
}

void calc_comp(){

    vector<int>vec1(m,-1);
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
        component[i][j] = -1;
    
    int cnt = 1;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            if(component[i][j]!=-1)continue;
            else colors[cnt] = vec[i][j],dfs(i,j,cnt++);
}

int main()
{
    // freopen("out.txt","w",stdout);
    scanf("%d%d",&n,&m);

    vector<int>vec0;
    vector<int>vec1(m,-1);
    
    for(int i=1;i<=n;i++){

        for(int j=0;j<m;j++){
            int x;cin>>x;
            vec0.push_back(x);
        }
        vec.push_back(vec0);
        vec0.clear();
        component.push_back(vec1);
    }
    
    calc_comp();
    
    int q;
    scanf("%d",&q);
    while(q--){
        int i,j,c;
        scanf("%d%d%d",&i,&j,&c);
        i--,j--;

        for(int i1=0;i1<n;i1++)
            for(int j1=0;j1<m;j1++)
            if(component[i1][j1]==component[i][j])vec[i1][j1] = c;

        calc_comp();
    }    

    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++)
            printf("%d ",colors[component[i][j]]);
        puts("");
    }
}

Compilation message

paint.cpp: In function 'int main()':
paint.cpp:63:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   63 |     scanf("%d%d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~
paint.cpp:82:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   82 |     scanf("%d",&q);
      |     ~~~~~^~~~~~~~~
paint.cpp:85:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   85 |         scanf("%d%d%d",&i,&j,&c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 364 KB Output is correct
2 Correct 6 ms 364 KB Output is correct
3 Correct 1140 ms 620 KB Output is correct
4 Correct 1808 ms 620 KB Output is correct
5 Correct 1723 ms 988 KB Output is correct
6 Correct 1979 ms 1388 KB Output is correct
7 Correct 1 ms 364 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3066 ms 1896 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3069 ms 3308 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 52.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3070 ms 2412 KB Time limit exceeded
2 Halted 0 ms 0 KB -