#include<bits/stdc++.h>
#define fi first
#define se second
#define ll long long
using namespace std ;
const ll N = 1e5 ;
ll ans, cnt[N + 1] ;
map<pair<ll, ll>, bool> mp ;
vector<int> v[N + 1], v1[N + 1] ;
signed main()
{
ios_base::sync_with_stdio( 0 ) ;
cin.tie( 0 ) ;
cout.tie( 0 ) ;
ll n, m ;
cin >> n >> m ;
if(n <= 50)
{
while(m--)
{
ll a, b ;
cin >> a >> b ;
if(!mp[{a, b}])
{
ans++ ;
mp[{a, b}] = 1 ;
}
bool flag = 1 ;
while(flag)
{
flag = 0 ;
for(ll x = 1 ; x <= n ; x++)
for(ll y = 1 ; y <= n ; y++)
{
if(x == y)
continue ;
for(ll z = 1 ; z <= n ; z++)
if(x != z && z != y && !mp[{x, z}] && mp[{x, y}] && mp[{y, z}] && mp[{z, y}])
{
flag = 1 ;
ans++ ;
mp[{x, z}] = 1 ;
}
}
}
cout << ans << '\n';
}
return 0 ;
}
if(n <= 2000)
{
while(m--)
{
ll x, y ;
cin >> x >> y ;
if(!mp[{x, y}])
{
ans++ ;
mp[{x, y}] = 1 ;
v[x].push_back(y) ;
v1[y].push_back(x) ;
// cout<<x<<"->"<<y << '\n' ;
}
deque<pair<int, int>> d ;
if(mp[{x, y}] && mp[{y, x}])
d.push_back({x, y}) ;
while(d.size())
{
int x1 = d[0].fi, y1 = d[0].se ;
d.pop_front() ;
for(ll i = 0 ; i < v1[y1].size() ; i++)
{
ll z = v1[y1][i] ;
if(z != x1 && !mp[{z, x1}])
{
mp[{z, x1}] = 1 ;
if(mp[{x1, z}])
d.push_back({z, x1}) ;
ans++ ;
v[z].push_back(x1) ;
// cout<<z<<"->"<<x1 << '\n' ;
v1[x1].push_back(z) ;
}
}
for(ll i = 0 ; i < v1[x1].size() ; i++)
{
ll z = v1[x1][i] ;
if(z != y1 && !mp[{z, y1}])
{
mp[{z, y1}] = 1 ;
if(mp[{y1, z}])
d.push_back({z, y1}) ;
ans++ ;
v[z].push_back(y1) ;
// cout<<z<<"->"<<y1 << '\n' ;
v1[y1].push_back(z) ;
}
}
for(ll i = 0 ; i < v[y1].size() ; i++)
{
ll z = v[y1][i] ;
if(z != x1 && !mp[{x1, z}] && mp[{z, y1}])
{
mp[{x1, z}] = 1 ;
ans++ ;
v[z].push_back(x1) ;
// cout<<z<<"->"<<x1 << '\n' ;
v1[x1].push_back(z) ;
}
}
}
for(ll i = 0 ; i < v[y].size() ; i++)
{
ll z = v[y][i] ;
if(z != x && !mp[{x, z}] && mp[{z, y}])
{
mp[{x, z}] = 1 ;
ans++ ;
v[z].push_back(x) ;
// cout<<z<<"->"<<x << '\n' ;
v1[x].push_back(z) ;
}
}
cout << ans << '\n' ;
}
return 0 ;
}
for(ll i = 1 ; i <= m ; i++)
{
ll x, y ;
cin >> x >> y ;
cout << ans << '\n' ;
}
return 0 ;
}
Compilation message
joitter2.cpp: In function 'int main()':
joitter2.cpp:71:34: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
71 | for(ll i = 0 ; i < v1[y1].size() ; i++)
| ~~^~~~~~~~~~~~~~~
joitter2.cpp:85:34: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
85 | for(ll i = 0 ; i < v1[x1].size() ; i++)
| ~~^~~~~~~~~~~~~~~
joitter2.cpp:99:34: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
99 | for(ll i = 0 ; i < v[y1].size() ; i++)
| ~~^~~~~~~~~~~~~~
joitter2.cpp:112:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
112 | for(ll i = 0 ; i < v[y].size() ; i++)
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 3 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 4 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 5 |
Correct |
4 ms |
4948 KB |
Output is correct |
| 6 |
Correct |
4 ms |
5028 KB |
Output is correct |
| 7 |
Execution timed out |
5091 ms |
5156 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 3 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 4 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 5 |
Correct |
4 ms |
4948 KB |
Output is correct |
| 6 |
Correct |
4 ms |
5028 KB |
Output is correct |
| 7 |
Execution timed out |
5091 ms |
5156 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 3 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 4 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 5 |
Correct |
4 ms |
4948 KB |
Output is correct |
| 6 |
Correct |
4 ms |
5028 KB |
Output is correct |
| 7 |
Execution timed out |
5091 ms |
5156 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
