oj.uz

Submission #158520

# Submission time Handle Problem Language Result Execution time Memory
158520 2019-10-17T14:36:33 Z alexandra_udristoiu Izlet (COI19_izlet) C++14
43 / 100
 1094 ms 36112 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];
        if(t[nod] != 0){
            adauga(t[nod], nod);
            memset(viz, 0, sizeof(viz) );
            memset(ff, 0, sizeof(ff) );
            viz[nod] = 1;
            dfs(t[nod], 0);
            if(s[nod] == 0){
                s[nod] = ++nr;
            }
            continue;
        }
        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){
            for(j = i + 1; j <= n; j++){
                if(a[nod][ w[j] ] == 2){
                    t[ w[i] ] = w[j];
                    swap(w[i], w[j]);
                    break;
                }
            }
            i--;
            continue;
        }
        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 632 KB Output is correct
2 Correct 913 ms 36012 KB Output is correct
3 Correct 923 ms 35944 KB Output is correct
4 Correct 844 ms 35856 KB Output is correct
5 Correct 885 ms 35760 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 927 ms 36088 KB Output is correct
2 Correct 857 ms 35824 KB Output is correct
3 Correct 1081 ms 36112 KB Output is correct
4 Correct 1094 ms 36088 KB Output is correct
5 Correct 845 ms 36040 KB Output is correct
6 Correct 893 ms 35944 KB Output is correct
7 Correct 645 ms 30388 KB Output is correct

Subtask #3
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB Output is correct
2 Correct 913 ms 36012 KB Output is correct
3 Correct 923 ms 35944 KB Output is correct
4 Correct 844 ms 35856 KB Output is correct
5 Correct 885 ms 35760 KB Output is correct
6 Correct 927 ms 36088 KB Output is correct
7 Correct 857 ms 35824 KB Output is correct
8 Correct 1081 ms 36112 KB Output is correct
9 Correct 1094 ms 36088 KB Output is correct
10 Correct 845 ms 36040 KB Output is correct
11 Correct 893 ms 35944 KB Output is correct
12 Correct 645 ms 30388 KB Output is correct
13 Incorrect 870 ms 36024 KB Output isn't correct
14 Halted 0 ms 0 KB -