| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 334628 |
2020-12-09T15:21:38 Z |
CaroLinda |
Flood (IOI07_flood) |
C++14 |
|
905 ms |
65540 KB |
#include <bits/stdc++.h>
#define debug printf
#define ll long long
#define all(x) x.begin(),x.end()
#define sz(x) (int)(x.size() )
const int MAX = 1e5+2 ;
const int MAXT = 4e5+10 ;
using namespace std ;
struct Bit
{
int bit[MAXT] ;
void upd(int i, int val) { for(; i < MAXT ; i += i &-i ) bit[i] += val ; }
int qry(int i)
{
int tot = 0 ;
for(; i > 0 ; i -= i &-i ) tot += bit[i] ;
return tot ;
}
} bit ;
int N , W ;
int dsu[MAX*4] , dist[MAX*4] ;
vector<int> adj[ MAX*4 ] ;
pair<int,int> points[MAX] , Lines[MAX*2] ;
map< pair<int,int> , int > vertices ;
set< pair<int,int> > vis ;
vector< tuple<int,int,int> > freq[2] , walls[2] ;
map<int,int> compression ;
void add( pair<int,int> p )
{
if( vertices.find(p) != vertices.end() ) return ;
vertices.insert( make_pair(p, sz(vertices)+1 ) ) ;
dsu[ sz(vertices) ] = sz(vertices) ;
freq[0].push_back( make_tuple(p.second,p.first, sz(vertices) ) ) ;
freq[1].push_back( make_tuple(p.first, p.second, sz(vertices) ) ) ;
}
int find(int x)
{
if(x == dsu[x] ) return x;
return dsu[x] = find(dsu[x] ) ;
}
void join(int x, int y )
{
x = find(x);
y = find(y) ;
if( x == y) return ;
if(rand() % 2 ) swap(x,y) ;
dsu[x] = y ;
}
void bfs(int s )
{
vector<int> fila(1,s) ;
int ini = 0 ;
dist[s] = 1 ;
while( ini < sz(fila ) )
{
int x = fila[ini++] ;
for(auto e : adj[x] )
{
if( dist[e] ) continue ;
dist[e] = dist[x] + 1 ;
fila.push_back(e) ;
}
}
}
int main()
{
scanf("%d", &N) ;
for(int i = 0 ; i < N ; i++ )
{
scanf("%d %d", &points[i].first, &points[i].second ) ;
compression[ points[i].first ] = 0 ;
compression[ points[i].second ] = 0 ;
}
scanf("%d", &W ) ;
for(int i = 0, A, B ; i < W ; i++ )
{
scanf("%d %d", &Lines[i].first, &Lines[i].second ) ;
Lines[i].first-- ;
Lines[i].second-- ;
A = Lines[i].first ;
B = Lines[i].second ;
compression[ points[A].first+1 ] = 0 ;
compression[ points[A].second+1 ] = 0 ;
compression[ points[B].first+1 ] = 0 ;
compression[ points[B].second+1 ] = 0 ;
}
int Key = 1 ;
for(auto &e : compression ) e.second = Key++ ;
for(int i= 0 ; i < N ; i++ )
{
points[i].first = compression[ points[i].first ] ;
points[i].second = compression[ points[i].second ] ;
add( make_pair( points[i].first, points[i].second) ) ;
add( make_pair( points[i].first+1, points[i].second) ) ;
add( make_pair( points[i].first, points[i].second+1) ) ;
add( make_pair( points[i].first+1, points[i].second+1) ) ;
}
for(int i = 0, A, B ; i < W ; i++ )
{
A = Lines[i].first ;
B = Lines[i].second ;
if( points[A].first == points[B].first )
{
if( points[B].second < points[A].second ) swap(A,B) ;
walls[0].push_back(make_tuple( points[A].second+1 , points[A].first+1,1) ) ;
walls[0].push_back(make_tuple( points[B].second+1, points[B].first+1 , -1) ) ;
Lines[i] = make_pair( vertices[make_pair(points[A].first,points[A].second+1)] , vertices[ make_pair(points[A].first+1, points[A].second+1)] ) ;
}
else
{
if( points[B].first < points[A].first ) swap(A,B) ;
walls[1].push_back(make_tuple( points[A].first+1, points[A].second+1, 1 ) ) ;
walls[1].push_back(make_tuple(points[B].first+1, points[B].second+1, -1) ) ;
Lines[i] = make_pair( vertices[make_pair(points[A].first+1, points[A].second) ], vertices[ make_pair(points[A].first+1, points[A].second+1) ] ) ;
}
}
//0 means I'm joining elements in the same row
//1 means I'm joining elements in the same column
for(int ori = 0 ; ori < 2 ; ori++ )
{
sort(all(freq[ori] ) ) ;
sort(all(walls[ori]) ) ;
int ptrFreq = 0 , ptrWalls = 0 ;
for(int i = 0 ; i < MAXT ; i++ )
{
while( ptrWalls < sz(walls[ori]) && get<0>(walls[ori][ptrWalls]) == i )
{
bit.upd( get<1>(walls[ori][ptrWalls]) , get<2>(walls[ori][ptrWalls]) ) ;
ptrWalls++ ;
}
int aux = ptrFreq ;
while( ptrFreq < sz(freq[ori] ) && get<0>(freq[ori][ptrFreq]) == i ) { ptrFreq++ ; }
for(; aux < ptrFreq - 1 ; aux++ )
{
if( bit.qry(get<1>(freq[ori][aux+1]) ) - bit.qry( get<1>(freq[ori][aux]) ) ) continue ;
int u = get<2>( freq[ori][aux] ) ;
int v = get<2>( freq[ori][aux+1] ) ;
join(u,v) ;
}
}
}
for(auto e : Lines )
{
adj[ find(e.first) ].push_back( find(e.second) ) ;
adj[ find(e.second) ].push_back( find(e.first) ) ;
}
for(auto e : vertices) vis.insert( make_pair(e.first.first, e.first.second ) ) ;
while( !vis.empty() )
{
int x = vertices[ make_pair( vis.begin()->first, vis.begin()->second) ] ;
vis.erase( vis.begin() ) ;
if( dist[find(x) ] ) continue ;
bfs( find(x) ) ;
}
vector<int> ans ;
for(int i = 0 ; i < W ; i++ )
if( dist[ find(Lines[i].first) ] == dist[ find(Lines[i].second) ] ) ans.push_back(i+1) ;
printf("%d\n", sz(ans ) ) ;
for(auto e :ans ) printf("%d\n", e ) ;
}
Compilation message
flood.cpp: In function 'int main()':
flood.cpp:92:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
92 | scanf("%d", &N) ;
| ~~~~~^~~~~~~~~~
flood.cpp:95:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
95 | scanf("%d %d", &points[i].first, &points[i].second ) ;
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
flood.cpp:101:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
101 | scanf("%d", &W ) ;
| ~~~~~^~~~~~~~~~~
flood.cpp:104:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
104 | scanf("%d %d", &Lines[i].first, &Lines[i].second ) ;
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
12128 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
12000 KB |
Output is correct |
| 2 |
Correct |
14 ms |
12000 KB |
Output is correct |
| 3 |
Correct |
15 ms |
12000 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
12000 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
12008 KB |
Output is correct |
| 2 |
Correct |
16 ms |
12136 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
12000 KB |
Output is correct |
| 2 |
Correct |
14 ms |
12000 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
12000 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
12128 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
12128 KB |
Output is correct |
| 2 |
Correct |
17 ms |
12264 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
12136 KB |
Output is correct |
| 2 |
Correct |
17 ms |
12128 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
152 ms |
27600 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
454 ms |
51656 KB |
Memory limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
508 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
867 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
905 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
