Submission #167300

#	Time	Username	Problem	Language	Result	Execution time	Memory
167300		umutcangs1	Izlet (COI19_izlet)	C++14	100 / 100	948 ms	96936 KiB

izlet

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define INF 9e18
#define M (ll)(1e5+5)
typedef long long ll;
typedef vector <ll> vi;
typedef pair <ll,ll> pll;
typedef vector <pll> vpll;
ll mx(ll a,ll b){if(a>=b) return a;return b;}
ll mn(ll a,ll b){if(a<b) return a;return b;}
ll c[3005][3005],cnt[3005],check[3005];
bool vis[3005];
vpll G;
vi g[3005];
struct dis{
    ll par[3005];
    ll baba(ll x){
        return par[x]==x ? x : (par[x]=baba(par[x]));
    }
    void uni(ll x,ll y){
        x=baba(x),y=baba(y);
        if(x!=y) par[x]=y;
    }
}d[2];
ll dfs2(ll u,ll p,ll cur){
    for(ll i=0;i<g[u].size();i++){
        ll v=g[u][i];
        if(!vis[v]) continue;
        if(v==p) continue;
        if(c[cur][u]==c[cur][v] and check[cnt[v]]==0)
            return cnt[v];
        check[cnt[v]]++;
        ll val=dfs2(v,u,cur);
        if(val!=-1) return val;
        check[cnt[v]]--;
    }
    return -1;
}
ll co=1;
void dfs1(ll u,ll p){
    vis[u]=1;
    for(ll i=0;i<3005;i++)
        check[i]=0;
    ll val=dfs2(u,0,u);
    if(val==-1) cnt[u]=co++;
    else cnt[u]=val;
    for(ll i=0;i<g[u].size();i++){
        ll v=g[u][i];
        if(v==p) continue;
        dfs1(v,u);
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    ll t,n;cin>>t>>n;
    for(ll i=1;i<=n;i++)
        d[0].par[i]=d[1].par[i]=i;
    for(ll i=1;i<=n;i++)
        for(ll j=1;j<=n;j++){
            cin>>c[i][j];
            if(c[i][j]==1 and d[0].baba(i)!=d[0].baba(j)){
                G.pb(mp(i,j));
                d[0].uni(i,j);
                d[1].uni(i,j);
            }
        }
    for(ll i=1;i<=n;i++)
        for(ll j=1;j<=n;j++)
            if(c[i][j]==2 and d[0].baba(i)!=d[0].baba(j)){
                G.pb(mp(i,j));
                d[0].uni(i,j);
                g[d[1].baba(i)].pb(d[1].baba(j));
                g[d[1].baba(j)].pb(d[1].baba(i));
            }
    dfs1(d[1].baba(1),0);
    for(ll i=1;i<=n;i++)
        cout<<cnt[d[1].baba(i)]<<" ";
    cout<<endl;
    for(ll i=0;i<n-1;i++)
        cout<<G[i].first<<" "<<G[i].second<<endl;
    return 0;
}

Compilation message (stderr)

izlet.cpp: In function 'll dfs2(ll, ll, ll)':
izlet.cpp:28:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(ll i=0;i<g[u].size();i++){
                ~^~~~~~~~~~~~
izlet.cpp: In function 'void dfs1(ll, ll)':
izlet.cpp:49:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(ll i=0;i<g[u].size();i++){
                ~^~~~~~~~~~~~

• Subtask 1: 18 / 18
• Subtask 2: 25 / 25
• Subtask 3: 57 / 57