# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
29108 | 2017-07-18T09:32:33 Z | dereotu | Crocodile's Underground City (IOI11_crocodile) | C++14 | 439 ms | 262144 KB |
#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]; } } } //cout<<"amk "<<x<<space<<best<<space<<secondbest<<endl; nodes[x]=secondbest; return; } else{ 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); forr(i,0,N){ //cout<<i<<space<<nodes[i]<<endl; } int ans=nodes[0]; return ans; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 0 ms | 119444 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Memory limit exceeded | 39 ms | 262144 KB | Memory limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 439 ms | 119444 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
2 | Halted | 0 ms | 0 KB | - |