oj.uz

Submission #158518

# Submission time Handle Problem Language Result Execution time Memory
158518 2019-10-17T14:15:38 Z alexandra_udristoiu Izlet (COI19_izlet) C++14
43 / 100
 2000 ms 61388 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){
            for(j = i + 1; j <= n; j++){
                if(a[nod][ w[j] ] == 2){
                    swap(w[i], w[j]);
                }
            }
            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 504 KB Output is correct
2 Correct 916 ms 36016 KB Output is correct
3 Correct 918 ms 35900 KB Output is correct
4 Correct 857 ms 35896 KB Output is correct
5 Correct 902 ms 35780 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 937 ms 36188 KB Output is correct
2 Correct 875 ms 36056 KB Output is correct
3 Correct 1083 ms 36056 KB Output is correct
4 Correct 1121 ms 36144 KB Output is correct
5 Correct 845 ms 35988 KB Output is correct
6 Correct 905 ms 35852 KB Output is correct
7 Correct 651 ms 30556 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 916 ms 36016 KB Output is correct
3 Correct 918 ms 35900 KB Output is correct
4 Correct 857 ms 35896 KB Output is correct
5 Correct 902 ms 35780 KB Output is correct
6 Correct 937 ms 36188 KB Output is correct
7 Correct 875 ms 36056 KB Output is correct
8 Correct 1083 ms 36056 KB Output is correct
9 Correct 1121 ms 36144 KB Output is correct
10 Correct 845 ms 35988 KB Output is correct
11 Correct 905 ms 35852 KB Output is correct
12 Correct 651 ms 30556 KB Output is correct
13 Correct 1195 ms 35904 KB Output is correct
14 Correct 1089 ms 61388 KB Output is correct
15 Execution timed out 2061 ms 53240 KB Time limit exceeded
16 Halted 0 ms 0 KB -