Submission #368131

#	Time	Username	Problem	Language	Result	Execution time	Memory
368131		SavicS	Crocodile's Underground City (IOI11_crocodile)	C++14	0 / 100	2 ms	2668 KiB

crocodile

#include "crocodile.h";

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>

#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define ff(i,a,b) for(int i=a;i<=b;i++)
#define fb(i,b,a) for(int i=b;i>=a;i--)

using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 100005;
const int inf = 1e9 + 5;

template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

// os.order_of_key(k) the number of elements in the os less than k
// *os.find_by_order(k)  print the k-th smallest number in os(0-based)

int n, m, k;

vector<pii> g[maxn];

bool mark[maxn];
bool spec[maxn]; // ovde ako udjem zavrsavam i treba da vidim do kojih mogu da dodjem

int br[maxn];
bool visited[maxn];
void dfs1(int v){
    visited[v] = 1;
    if(mark[v]){
        for(auto c : g[v]){
            int u = c.fi;
            int w = c.se;
            if(!visited[u])dfs1(u);
        }
        return;
    }
    for(auto c : g[v]){
        int u = c.fi;
        int w = c.se;
        if(!visited[u]){
            dfs1(u);
        }
        if(mark[u] == 1)br[v] += 1;
    }
}

bool was[maxn];
void dfs2(int v){
    cout << "v: " << v << endl;
    was[v] = 1;
    if(mark[v] == 1 || spec[v] == 1){
        for(auto c : g[v]){
            int u = c.fi;
            int w = c.se;
            if(!was[u])dfs2(u);
        }
        return;
    }
    for(auto c : g[v]){
        int u = c.fi;
        int w = c.se;
        if(!was[u]){
            dfs2(u);
        }
        if(spec[u] == 1)br[v] += 1;
    }
}

ll dist[maxn];
void dij(int sv){
    ff(i,1,n)dist[i] = inf;
    priority_queue<pii> pq;
    pq.push({dist[sv] = 0, sv});
    while(!pq.empty()){
        pii v = pq.top();pq.pop();
        if(dist[v.se] < -v.fi)continue;
        for(auto c : g[v.se]){
            int u = c.fi;
            int w = c.se;
            if(dist[u] > w + -v.fi){
                dist[u] = -v.fi + w;
                pq.push({-dist[u], u});
            }
        }
    }
}

vector<int> koji;
bool used[maxn];
void dfs3(int v){
    used[v] = 1;
    if(spec[v]){
        koji.pb(v);
        return;
    }
    if(br[v] == 0)return;
    for(auto c : g[v]){
        int u = c.fi;
        int w = c.se;
        if(!used[u]){
            if(br[v] > 1)dfs3(u);
            else{
                if(br[v] == 1 && (mark[u] || spec[u]))continue;
            }
        }
    }
}

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
    n = N;
    m = M;
    k = K;
    ff(i,0,m - 1){
        int u = R[i][0];
        int v = R[i][1];
        int w = L[i];
        g[u].pb({v, w});
        g[v].pb({u, w});
    }
    ff(i,0,k - 1){
        int x = P[i];
        mark[x] = 1;
    }
    // moram da vidim koji cvor ima >= 2 izlaza
    // i onda samo uzimam drugi najmanju
    dfs1(1);
    ff(i,1,n){
        if(br[i] >= 2)spec[i] = 1;
    }
    dfs2(1);
    // sad treba videti do kojih specijalnih mogu doci
    dfs3(1);
    dij(1);
    vector<int> svi;
    for(auto c : koji){
        int mn1 = inf;
        int mn2 = inf;
        for(auto f : g[c]){
            int u = f.fi;
            if(mark[u]){
                if(dist[u] < mn1){
                    mn2 = mn1;
                    mn1 = dist[u];
                }
                else{
                    if(dist[u] < mn2)mn2 = dist[u];
                }
            }
        }
        if(mn2 != inf)svi.pb(mn2);
        else svi.pb(mn1);
    }
    sort(all(svi));
    return svi.back();
}

//bool cmp(int s1, int s2){
//    return dist[s1] < dist[s2];
//}
//
//int main()
//{
//    ios::sync_with_stdio(false);
//    cout.tie(nullptr);
//    cin.tie(nullptr);
//    cin >> n >> m >> k;
//    ff(i,1,k){
//        int x;
//        cin >> x;
//        mark[x] = 1;
//    }
//    ff(i,1,m){
//        int u, v, w;
//        cin >> u >> v >> w;
//        g[u].pb({v, w});
//        g[v].pb({u, w});
//    }
//    // moram da vidim koji cvor ima >= 2 izlaza
//    // i onda samo uzimam drugi najmanju
//    dfs1(1);
//    ff(i,1,n){
//        if(br[i] >= 2)spec[i] = 1;
//    }
//    dfs2(1);
//    // sad treba videti do kojih specijalnih mogu doci
//    dfs3(1);
//    dij(1);
//    vector<int> svi;
//    for(auto c : koji){
//        int mn1 = inf;
//        int mn2 = inf;
//        for(auto f : g[c]){
//            int u = f.fi;
//            if(mark[u]){
//                if(dist[u] < mn1){
//                    mn2 = mn1;
//                    mn1 = dist[u];
//                }
//                else{
//                    if(dist[u] < mn2)mn2 = dist[u];
//                }
//            }
//        }
//        if(mn2 != inf)svi.pb(mn2);
//        else svi.pb(mn1);
//    }
//    sort(all(svi));
//    cout << svi.back() << endl;
//    return 0;
//}
/**

5 4 3
2 4 5
1 2 2
1 3 3
4 3 1
3 5 4

8 7 4
4 5 7 8
1 2 1
2 3 1
3 4 1
3 5 1
1 6 1
6 7 1
6 8 1

5 7 2
2 4
1 3 4
1 4 3
4 3 2
3 2 10
1 2 100
1 5 7
4 5 9

// probati bojenje sahovski ili slicno

**/

Compilation message (stderr)

crocodile.cpp:1:23: warning: extra tokens at end of #include directive
    1 | #include "crocodile.h";
      |                       ^
crocodile.cpp: In function 'void dfs1(int)':
crocodile.cpp:43:17: warning: unused variable 'w' [-Wunused-variable]
   43 |             int w = c.se;
      |                 ^
crocodile.cpp:50:13: warning: unused variable 'w' [-Wunused-variable]
   50 |         int w = c.se;
      |             ^
crocodile.cpp: In function 'void dfs2(int)':
crocodile.cpp:65:17: warning: unused variable 'w' [-Wunused-variable]
   65 |             int w = c.se;
      |                 ^
crocodile.cpp:72:13: warning: unused variable 'w' [-Wunused-variable]
   72 |         int w = c.se;
      |             ^
crocodile.cpp: In function 'void dfs3(int)':
crocodile.cpp:110:13: warning: unused variable 'w' [-Wunused-variable]
  110 |         int w = c.se;
      |             ^

• Subtask 1: 0 / 46
• Subtask 2: 0 / 43
• Subtask 3: 0 / 11