| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 137407 | 2019-07-27T16:30:20 Z | CaroLinda | Simurgh (IOI17_simurgh) | C++14 | 2 ms | 632 KB |
#include <bits/stdc++.h>
#include "simurgh.h"
#define debug printf
#define lp(i,a,b) for(int i=a;i<b;i++)
#define pii pair<int,int>
#define ll long long
#define ff first
#define ss second
#define pb push_back
#define mk make_pair
const int MAXN = 510 ;
const int MAXM = 510*510 ;
using namespace std ;
struct Edge
{
int j , id ;
Edge(int j = 0 , int id = 0 )
: j(j) , id(id) {}
} ;
int enterTime ;
int height[MAXN] , lowlink[MAXN] , ini[MAXN] , fim[MAXN] , pai[MAXN] ;
pii listEdges[MAXM] ;
vector<Edge> adj[MAXN] ;
bool isBridge[MAXM] , marc[MAXM] , royal[MAXN] ;
vector<int> randomTree ;
// ----------------------------------
void dfs(int x, int depth )
{
height[x] = lowlink[x] = depth ;
for( Edge e : adj[x] )
{
if( marc[e.id] ) continue ;
marc[e.id] = true ;
if( height[e.j] != -1 )
{ lowlink[x] = min( lowlink[x] , height[e.j] ) ; continue ; }
dfs(e.j, depth+1 ) ;
lowlink[x] = min( lowlink[e.j] , lowlink[x] ) ;
if( lowlink[e.j] >= height[e.j] )
{
isBridge[e.id] = true ;
royal[e.id] = true ;
}
}
}
void findRandomTree(int x)
{
marc[x] = true ;
ini[x] = ++ enterTime ;
for( Edge e : adj[x] )
{
if( marc[e.j] ) continue ;
randomTree.pb( e.id ) ;
pai[e.j] = x ;
findRandomTree(e.j) ;
}
fim[x] = enterTime ;
}
vector<int> find_roads(int n, vector<int> u, vector<int> v)
{
lp(i,0, u.size() )
{
int a = u[i] , b = v[i] ;
adj[a].pb( Edge(b,i) ) ;
adj[b].pb( Edge(a,i) ) ;
listEdges[i] = mk(a,b) ;
}
memset( height, -1 , sizeof height ) ;
dfs(0,1) ;
pai[0] = -1 ;
memset(marc, false, sizeof marc ) ;
findRandomTree(0) ;
lp(i,0,u.size())
{
int ini1 = listEdges[i].ff ;
int ini2 = listEdges[i].ss ;
if( ini1 < ini2 ) swap(listEdges[i].ff, listEdges[i].ss ) ;
}
int num = count_common_roads(randomTree) ;
lp(g,0,randomTree.size() )
{
int i = randomTree[g] ;
if( isBridge[i] ) continue ;
bool imRoyal = true ;
vector<int> equalToMe ; equalToMe.pb(i) ;
pii p = listEdges[i] ;
lp(j , 0, u.size())
{
if(isBridge[j]) continue ;
if( !(ini[ listEdges[j].ff ] > ini[p.ff] && fim[listEdges[j].ss] <= fim[p.ff]) ) continue ;
if( ini[listEdges[j].ss] > ini[p.ff] && fim[listEdges[j].ss] <= fim[p.ff] ) continue ;
randomTree[g] = j ;
int newNum = count_common_roads(randomTree) ;
randomTree[g] = i ;
if(newNum == num) equalToMe.pb(j) ;
else if(newNum > num)
{
royal[j] = true ;
imRoyal = false ;
}
}
if(imRoyal)
for(int j : equalToMe)
royal[j] = true ;
}
vector<int> ans ;
lp(i,0, u.size() )
if( royal[i] )
ans.pb(i) ;
return ans ;
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 2 ms | 632 KB | WA in grader: NO |
| 2 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 2 ms | 632 KB | WA in grader: NO |
| 2 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 2 ms | 632 KB | WA in grader: NO |
| 2 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 2 ms | 632 KB | correct |
| 2 | Incorrect | 2 ms | 632 KB | WA in grader: NO |
| 3 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 2 ms | 632 KB | WA in grader: NO |
| 2 | Halted | 0 ms | 0 KB | - |