oj.uz

Submission #173858

# Submission time Handle Problem Language Result Execution time Memory
173858 2020-01-05T15:23:34 Z alexandra_udristoiu Izlet (COI19_izlet) C++14
43 / 100
 1105 ms 43128 KB 
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
#include<cstring>
#define DIM 3005
using namespace std;
int tip, n, i, j, nr, nod;
int a[DIM][DIM], s[DIM], t[DIM], viz[DIM], w[DIM], ff[DIM];
vector<int> v[DIM];
int cmp(int x, int y){
    if(a[1][x] == a[1][y]){
        return x < y;
    }
    return a[1][x] < a[1][y];
}
void dfs(int curr, int nr){
    viz[curr] = 1;
    ff[ s[curr] ]++;
    if(ff[ s[curr] ] == 1){
        nr++;
    }
    if(a[curr][nod] == nr && s[nod] == 0){
        s[nod] = s[curr];
    }
    for(int i = 0; i < v[curr].size(); i++){
        int vecin = v[curr][i];
        if(viz[vecin] == 0){
            dfs(vecin, nr);
        }
    }
    ff[ s[curr] ]--;
}
void adauga(int x, int y){
    v[x].push_back(y);
    v[y].push_back(x);
}
int main(){
    scanf("%d%d", &tip, &n);
    for(i = 1; i <= n; i++){
        w[i] = i;
        for(j = 1; j <= n; j++){
            scanf("%d", &a[i][j]);
        }
    }
    sort(w + 1, w + n + 1, cmp);
    s[1] = nr = 1;
    for(i = 2; i <= n; i++){
        nod = w[i];
        for(j = i - 1; j >= 1; j--){
            if(a[1][ w[j] ] == a[1][nod] && a[ w[j] ][nod] == 1){
                s[nod] = s[ w[j] ];
                t[nod] = w[j];
                adauga(t[nod], nod);
                break;
            }
        }
        if(s[nod] != 0){
            continue;
        }
        for(j = 1; j < i; j++){
            if(a[ w[j] ][nod] == 2){
                t[nod] = w[j];
                adauga(t[nod], nod);
                break;
            }
        }
        if(t[nod] != 0){
            memset(viz, 0, sizeof(viz) );
            memset(ff, 0, sizeof(ff) );
            viz[nod] = 1;
            dfs(t[nod], 0);
            if(s[nod] == 0){
                s[nod] = ++nr;
            }
            for(j = i - 1; j >= 1; j--){
                if(t[ w[j] ] == 0 && a[ w[i] ][ w[j] ] == 2){
                    t[ w[j] ] = w[i];
                    adauga(w[i], w[j]);
                    nod = w[j];
                    memset(viz, 0, sizeof(viz) );
                    memset(ff, 0, sizeof(ff) );
                    viz[nod] = 1;
                    dfs(t[nod], 0);
                    if(s[nod] == 0){
                        s[nod] = ++nr;
                    }
                }
            }
        }
    }
    for(i = 1; i <= n; i++){
        cout<< s[i] <<" ";
    }
    cout<<"\n";
    for(i = 2; i <= n; i++){
        cout<< i <<" "<< t[i] <<"\n";
    }
}

Compilation message

izlet.cpp: In function 'void dfs(int, int)':
izlet.cpp:26:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < v[curr].size(); i++){
                    ~~^~~~~~~~~~~~~~~~
izlet.cpp: In function 'int main()':
izlet.cpp:39:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &tip, &n);
     ~~~~~^~~~~~~~~~~~~~~~~~
izlet.cpp:43:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &a[i][j]);
             ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 949 ms 40344 KB Output is correct
3 Correct 954 ms 41068 KB Output is correct
4 Correct 875 ms 40344 KB Output is correct
5 Correct 922 ms 40412 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 976 ms 40072 KB Output is correct
2 Correct 895 ms 39748 KB Output is correct
3 Correct 1105 ms 43128 KB Output is correct
4 Correct 1101 ms 42232 KB Output is correct
5 Correct 872 ms 38236 KB Output is correct
6 Correct 915 ms 38580 KB Output is correct
7 Correct 666 ms 31964 KB Output is correct

Subtask #3
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 949 ms 40344 KB Output is correct
3 Correct 954 ms 41068 KB Output is correct
4 Correct 875 ms 40344 KB Output is correct
5 Correct 922 ms 40412 KB Output is correct
6 Correct 976 ms 40072 KB Output is correct
7 Correct 895 ms 39748 KB Output is correct
8 Correct 1105 ms 43128 KB Output is correct
9 Correct 1101 ms 42232 KB Output is correct
10 Correct 872 ms 38236 KB Output is correct
11 Correct 915 ms 38580 KB Output is correct
12 Correct 666 ms 31964 KB Output is correct
13 Incorrect 906 ms 36900 KB Output isn't correct
14 Halted 0 ms 0 KB -