#include "bits/stdc++.h"
using namespace std;
#define endl '\n'
#define INF 1000000000000
#define mp make_pair
typedef int ll;
const int DIM=2e5+7;
ll n,m,k;
vector< pair<ll,ll> > a[DIM],b[DIM],flights;
ll mark[DIM];
vector<ll> v[2*DIM],topological;
ll vis[DIM*2];
ll scc[2*DIM];
void dfs(ll u, ll par)
{
vis[u]=1;
for (auto x:v[u])
{
if (vis[x]) continue;
dfs(x,u);
}
//cout << u << ' ' << par << endl;
topological.push_back(u);
}
void dfs2(ll u)
{
scc[u]=1;
for (auto x:v[u])
{
if (scc[x]) continue;
//cout << "go " << x << "from " << u << endl;
dfs2(x);
}
//cout << u << " ";
}
int main()
{
//freopen ("input.txt","r",stdin);
//freopen ("output.txt","w",stdout);
cin >> n >> m;
cin >> k;
for (int i=1;i<=k;i++)
{
int x,y;
cin >> x >> y;
a[x].push_back(mp(y,i));
b[y].push_back(mp(x,i));
flights.push_back(mp(x,y));
}
ll x=1;
ll y=1;
while(x<=n)
{
if (a[x].size()==0)
{
x++;
continue;
}
bool fl=0;
ll lim=-1;
ll num=0;
for (auto y:a[x])
{
if (y.first>lim)
{
lim=y.first;
num=y.second;
}
}
mark[num]=1;
for (auto y:a[x])
{
if (mark[y.second]==0) mark[y.second]=1;
}
//cout << "start " << x << " " << y << " " << lim << endl;
while(1)
{
//cout << x << ' ' << y << " " << lim << " " << fl << endl;
if (!fl)
{
bool check=1;
if (y==lim)
{
for (auto to:b[y])
{
if (mark[to.second]==0)
{
check=0;
break;
}
}
if (check)
{
y++;
x++;
break;
}
}
ll lim_x=x;
for (;y<=lim;y++)
{
if(b[y].size()==0) continue;
for (auto t:b[y])
{
if (mark[t.second]!=0) {continue;cout << "! " << y << endl;}
mark[t.second]=2;
//cout << "here 2 " << t.second << endl;
lim_x=max(lim_x,t.first);
}
}
y--;
lim=lim_x;
fl=1;
}
else
{
bool check=1;
if (x==lim)
{
for (auto to:a[x])
{
if (mark[to.second]==0)
{
check=0;
break;
}
}
if (check)
{
y++;
x++;
break;
}
}
ll lim_y=y;
for (;x<=lim;x++)
{
if(a[x].size()==0) continue;
for (auto t:a[x])
{
if (mark[t.second]!=0) continue;
mark[t.second]=1;
//cout << "here 1 " << t.second << endl;
lim_y=max(lim_y,t.first);
}
}
x--;
lim=lim_y;
fl=0;
}
}
}
for (int i=1;i<n;i++)
{
v[2*i-1].push_back(2*(i+1)-1);
}
for (int i=1;i<m;i++)
{
v[2*i].push_back(2*(i+1));
}
for (int i=1;i<=k;i++)
{
ll x=flights[i-1].first;
ll y=flights[i-1].second;
if (mark[i]==1)
{
v[2*y].push_back(2*x-1);
}
else
{
v[2*x-1].push_back(2*y);
}
}
for (int i=1;i<=n;i++)
{
if (!vis[2*i-1]) dfs(2*i-1,2*i-1);
}
for (int i=1;i<=m;i++)
{
if (!vis[2*i]) dfs(2*i,2*i);
}
//reverse(topological.begin(),topological.end());
ll c=0;
for (auto x:topological)
{
//cout << x << endl;
if (scc[x]==0)
{
dfs2(x);//cout << endl;
c++;
}
}
cout << c << endl;
for (int i=1;i<=k;i++)
{
if (mark[i]==1) cout << 1 << " ";
else cout << 0 << " ";
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
19036 KB |
Output is correct |
| 2 |
Incorrect |
10 ms |
19036 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
19036 KB |
Output is correct |
| 2 |
Incorrect |
10 ms |
19036 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
19036 KB |
Output is correct |
| 2 |
Incorrect |
10 ms |
19036 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
