# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
29113 | dereotu | Crocodile's Underground City (IOI11_crocodile) | C++14 | 389 ms | 262144 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "crocodile.h"
#include <bits/stdc++.h>
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define st first
#define nd second
#define forr(i,A,B) for(int i=A;i<B;++i)
#define space ' '
#define endl '\n'
#define LL long long
#define exit adsjdsa
using namespace std;
vector < pair<int,int> > adj[1005];
int exit[1005];
int cycle[1005];
int nodes[1005];
int neighbour[1005];
void dfs(int x,int y){
int best=1e9,secondbest=1e9;
if(exit[x]){
nodes[x]=0;
return;
}
if(cycle[x] and neighbour[x]>=2){
forr(i,0,adj[x].size()){
if(adj[x][i].nd!=y and (!cycle[adj[x][i].nd] or neighbour[adj[x][i].nd]>=2)){
dfs(adj[x][i].nd,x);
}
}
forr(i,0,adj[x].size()){
//cout<<"geziş "<<x<<space<<adj[x][i].nd<<space<<exit[adj[x][i].nd]<<endl;
if(exit[adj[x][i].nd]){
//cout<<adj[x][i].st<<endl;
if(adj[x][i].st<best){
secondbest=best;
best=adj[x][i].st;
}
else if(adj[x][i].st<secondbest){
secondbest=adj[x][i].st;
}
}
else if(neighbour[adj[x][i].nd]>=2 or !cycle[adj[x][i].nd]){
if(adj[x][i].nd!=y and adj[x][i].st+nodes[adj[x][i].nd]<best){
secondbest=best;
best=adj[x][i].st+nodes[adj[x][i].nd];
}
else if(adj[x][i].nd!=y and adj[x][i].st+nodes[adj[x][i].nd]<secondbest){
secondbest=adj[x][i].st+nodes[adj[x][i].nd];
}
}
}
nodes[x]=secondbest;
return;
}
else if(cycle[x] and neighbour[x]<2){
nodes[x]=1e9;
return;
}
forr(i,0,adj[x].size()){
if(adj[x][i].nd!=y){
dfs(adj[x][i].nd,x);
}
}
forr(i,0,adj[x].size()){
if(adj[x][i].nd!=y and adj[x][i].st+nodes[adj[x][i].nd]<best){
secondbest=best;
best=adj[x][i].st+nodes[adj[x][i].nd];
}
else if(adj[x][i].nd!=y and adj[x][i].st+nodes[adj[x][i].nd]<secondbest){
secondbest=adj[x][i].st+nodes[adj[x][i].nd];
}
}
nodes[x]=secondbest;
}
int visited[1005];
void cycle_detect(int x,int y){
if(visited[x]){
cycle[x]=1;
return;
}
visited[x]=1;
forr(i,0,adj[x].size()){
if(adj[x][i].nd!=y){
cycle_detect(adj[x][i].nd,x);
}
}
}
void neighbour_calc(int x){
visited[x]=1;
forr(i,0,adj[x].size()){
if(!visited[adj[x][i].nd]){
neighbour_calc(adj[x][i].nd);
}
if(neighbour[adj[x][i].nd]>=2) neighbour[x]++;
if(exit[adj[x][i].nd]) neighbour[x]++;
}
}
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
forr(i,0,M){
adj[R[i][0]].pb(mp(L[i],R[i][1]));
adj[R[i][1]].pb(mp(L[i],R[i][0]));
}
forr(i,0,K){
exit[P[i]]=1;
}
forr(i,0,N){
memset(visited,0,sizeof visited);
cycle_detect(i,-1);
}
memset(visited,0,sizeof visited);
neighbour_calc(0);
dfs(0,-1);
int ans=nodes[0];
return ans;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |