oj.uz

Submission #129653

# Submission time Handle Problem Language Result Execution time Memory
129653 2019-07-12T22:05:22 Z pzdba Izlet (COI19_izlet) C++14
100 / 100
 1086 ms 74760 KB 
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
int c[3002][3002], cnt[3002];
vector<pii> edge;
vector<int> g[3002];
struct dsu{
    int p[3002];
    int root(int a){
        return p[a] == a?a:(p[a]=root(p[a]));
    }
    void merge(int a, int b){
        a = root(a), b = root(b);
        if(a != b) p[a] = b;
    }
}d[2];

bool vis[3002];
int check[3002];
int dfs2(int u, int p, int cur){
    for(int i=0;i<g[u].size();i++){
        int v = g[u][i];
        if(!vis[v]) continue;
        if(v == p) continue;

        if(c[cur][u] == c[cur][v] && check[cnt[v]] == 0) return cnt[v];

        check[cnt[v]]++;
        int val = dfs2(v, u, cur);
        if(val != -1) return val;
        check[cnt[v]]--;
    }
    return -1;
}

int co = 1;
void dfs1(int u, int p){
    vis[u] = 1;

    memset(check, 0, sizeof(check));
    int val = dfs2(u, 0, u);
    if(val == -1) cnt[u] = co++;
    else cnt[u] = val;

    for(int i=0;i<g[u].size();i++){
        int v = g[u][i];
        if(v == p) continue;
        dfs1(v, u);
    }
}

int main(){
    int t, n;
    scanf("%d", &t);
    scanf("%d", &n);
    for(int i=1;i<=n;i++) d[0].p[i] = d[1].p[i] = i;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            scanf("%d", &c[i][j]);
            if(c[i][j] == 1 && d[0].root(i) != d[0].root(j)){
                edge.push_back(pii(i, j));
                d[0].merge(i, j);
                d[1].merge(i, j);
            }
        }
    }

    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(c[i][j] == 2 && d[0].root(i) != d[0].root(j)){
                edge.push_back(pii(i, j));
                d[0].merge(i, j);
                g[d[1].root(i)].push_back(d[1].root(j));
                g[d[1].root(j)].push_back(d[1].root(i));
            }
        }
    }

    dfs1(d[1].root(1), 0);
    for(int i=1;i<=n;i++) printf("%d ", cnt[d[1].root(i)]);
    printf("\n");
    for(int i=0;i<n-1;i++) printf("%d %d\n", edge[i].first, edge[i].second);
}

Compilation message

izlet.cpp: In function 'int dfs2(int, int, int)':
izlet.cpp:21:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<g[u].size();i++){
                 ~^~~~~~~~~~~~
izlet.cpp: In function 'void dfs1(int, int)':
izlet.cpp:45:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<g[u].size();i++){
                 ~^~~~~~~~~~~~
izlet.cpp: In function 'int main()':
izlet.cpp:54:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &t);
     ~~~~~^~~~~~~~~~
izlet.cpp:55:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
izlet.cpp:59:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &c[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 851 ms 36084 KB Output is correct
3 Correct 857 ms 36032 KB Output is correct
4 Correct 850 ms 35836 KB Output is correct
5 Correct 852 ms 35804 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 817 ms 35928 KB Output is correct
2 Correct 857 ms 53384 KB Output is correct
3 Correct 1036 ms 74056 KB Output is correct
4 Correct 1086 ms 74760 KB Output is correct
5 Correct 827 ms 53624 KB Output is correct
6 Correct 851 ms 60584 KB Output is correct
7 Correct 622 ms 49220 KB Output is correct

Subtask #3
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 851 ms 36084 KB Output is correct
3 Correct 857 ms 36032 KB Output is correct
4 Correct 850 ms 35836 KB Output is correct
5 Correct 852 ms 35804 KB Output is correct
6 Correct 817 ms 35928 KB Output is correct
7 Correct 857 ms 53384 KB Output is correct
8 Correct 1036 ms 74056 KB Output is correct
9 Correct 1086 ms 74760 KB Output is correct
10 Correct 827 ms 53624 KB Output is correct
11 Correct 851 ms 60584 KB Output is correct
12 Correct 622 ms 49220 KB Output is correct
13 Correct 838 ms 54352 KB Output is correct
14 Correct 989 ms 61300 KB Output is correct
15 Correct 849 ms 53452 KB Output is correct
16 Correct 949 ms 57908 KB Output is correct
17 Correct 967 ms 59860 KB Output is correct
18 Correct 835 ms 53624 KB Output is correct
19 Correct 871 ms 53356 KB Output is correct
20 Correct 882 ms 53388 KB Output is correct
21 Correct 857 ms 54124 KB Output is correct
22 Correct 857 ms 53748 KB Output is correct
23 Correct 872 ms 54216 KB Output is correct
24 Correct 918 ms 60504 KB Output is correct
25 Correct 832 ms 53652 KB Output is correct