oj.uz

Submission #559383

# Submission time Handle Problem Language Result Execution time Memory
559383 2022-05-09T17:00:44 Z leaked Izlet (COI19_izlet) C++17
0 / 100
 2000 ms 35780 KB 
#include <bits/stdc++.h>

#define f first
#define s second
#define m_p make_pair
#define vec vector
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define sz(x) (int)(x).size()
#define pw(x) (1LL<<(x))

using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
template<class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}
template<class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
const int N=3e3+1;
//int c[N][N];
//struct dsu{
//    int p[N];
//    dsu(){
//        iota(p,p+N,0);
//    }
//    int get(int v){
//        return p[v]=(p[v]==v?v:get(p[v]));
//    }
//    bool mg(int a,int b,int need=0){
//        a=get(a),b=get(b);
//        if(a==b) return 0;
//        if(need){
//            for(int i=0;i<n;i++)
//                assert(c[a][i]==c[b][i]);
//        }
//        p[a]=b;
//        return 1;
//    }
//}ds;

vec<int> have;
bool used[N];
int n;
int x[N][N],clr[N],cnt;
vec<pii> e;
void dfs(int v){
    used[v]=1;
    have.pb(v);
    for(int u=0;u<n;u++){
//        if(u!=ds.get(u)) continue;
        if(!used[u] && x[v][u]<=2){
            if(x[v][u]==1){
                clr[u]=clr[v];
                e.pb({v,u});
                dfs(u);
//                cout<<"E "<<v<<' '<<ue
                continue;
            }
            int ok=1;
            int j=-1;
//            e.pb({v,u})
            for(auto &z : have){
                if(!ok) break;
//                ok&=(x[v][z]==x[u][z]);
                if(x[v][z]==x[u][z]){
//                    cout<<"YO "<<v<<' '<<z<<' '<<u<<' '<<z<<endl;
                    if(j==-1){
                        j=z;
                    }
                    else
                        ok&=(clr[j]==clr[z]);
                }
            }
            for(auto &z : have){
                if(!ok) break;
//                ok&=(x[v][z]==x[u][z]);
                if(x[v][z]==x[u][z]){
//                    cout<<"YO "<<v<<' '<<z<<' '<<u<<' '<<z<<endl;
                    if(j==-1){
                        j=z;
                    }
                    else
                        ok&=(clr[j]==clr[z]);
                }
//                else if(x[])
                else if(x[v][z]!=x[u][z]-1 || (j!=-1 && clr[j]==clr[z]))
                    ok=0;
            }
            for(int tk=0;ok && tk<n;tk++){
                if(!used[tk])
                    ok&=(abs(x[v][tk]-x[u][tk])<=1);
            }
            if(ok){
                e.pb({v,u});
                if(j==-1)
                    clr[u]=++cnt;
                else
                    clr[u]=clr[j];
                dfs(u);
            }
        }
    }
}
signed main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int t;
    cin>>t>>n;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++)
            cin>>x[i][j];
//        for(int j=0;j<n;j++){
//            if(c[i][j]==1)
//                ds.mg(i,j,1);
//        }
    }
    clr[0]=++cnt;
    dfs(0);
    for(int i=0;i<n;i++){
        cout<<clr[i]<<' ';
    }
    cout<<'\n';
    for(auto &z : e)
        cout<<z.f+1<<' '<<z.s+1<<endl;
    return 0;
}
/*

*/

Subtask #1
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 546 ms 35560 KB Output is correct
3 Correct 496 ms 35604 KB Output is correct
4 Correct 494 ms 35716 KB Output is correct
5 Execution timed out 2084 ms 35780 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 469 ms 35532 KB Integer 0 violates the range [1, 3000]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 546 ms 35560 KB Output is correct
3 Correct 496 ms 35604 KB Output is correct
4 Correct 494 ms 35716 KB Output is correct
5 Execution timed out 2084 ms 35780 KB Time limit exceeded
6 Halted 0 ms 0 KB -