#include <bits/stdc++.h>
#define FLASH ios_base::sync_with_stdio(0);
#define ll long long
#define debt(x,y)cout<<"#x = "<<(x)<<" and "<<"#y = "<<(y)<<endl;
#define deb(x)cout<<"#x = "<<(x)<<endl;
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define endl "\n"
#define arr(a,n) for(ll i=1;i<=n;i++) cout<<a[i]<<" "; cout << "\n";
#define vecc(a,n) for(ll i=0;i<n;i++) cout<<a[i]<<" "; cout << "\n";
using namespace std;
ll n,m,k;
vector<ll>adj[300010];
vector<ll>adj1[300010];
vector<ll>adj2[300010];
ll dp[300010];
ll deg[300010];
ll color[300010];
vector<ll>tmp;
ll used[300010];
ll sig1[300010];
ll push[300010];
ll rankk[300010];
ll par[300010];
void make_set(ll n)
{
for(ll i=1;i<=n;i++)rankk[i]=1,par[i]=i;
}
ll findd(ll v)
{
while(par[v]!=v)
{
par[v]=par[par[v]];
v=par[v];
}
return v;
}
void make_union(ll a,ll b)
{
a=findd(a);
b=findd(b);
if(a!=b)
{
if(rankk[a]>rankk[b])swap(a,b);
par[a]=par[b];
rankk[b]+=rankk[a];
}
}
ll checkk(ll a,ll b)
{
if(findd(a)!=findd(b))return 1;
else return 0;
}
vector<ll>tops;
void dfs(ll v)
{
used[v]=1;
for(auto to:adj1[v])
{
if(used[to]==0)
{
dfs(to);
}
}
tops.pb(v);
}
void dfs1(ll v)
{
used[v]=1;
color[v]=n-dp[v]+1;
for(auto to:adj1[v])
{
if(used[to]==0 && dp[v]-1==dp[to])
{
dfs1(to);
}
}
}
ll mx=0;
vector<ll>el;
vector< pair<ll,ll> >edges;
int main(){
FLASH;
cin>>n>>m>>k;
make_set(m);
for(ll i=1;i<=k;i++)
{
string stroka;
cin>>stroka;
char sig;
ll cis1=0,cis2=0;
ll j=0;
for(;j<(ll)stroka.size();j++)
{
if(isdigit(stroka[j]))cis1=(cis1*10+(stroka[j]-'0'));
else break;
}
sig=stroka[j];
j++;
for(;j<(ll)stroka.size();j++)
{
if(isdigit(stroka[j]))cis2=(cis2*10+(stroka[j]-'0'));
else break;
}
if(sig=='=')
{
make_union(cis1,cis2);
}
else edges.pb(mp(cis1,cis2));
}
for(auto i:edges)
{
ll cis1=i.first;
ll cis2=i.second;
cis1=findd(cis1);
cis2=findd(cis2);
adj1[cis1].pb(cis2);
adj2[cis2].pb(cis1);
deg[cis2]++;
}
for(ll i=1;i<=m;i++)
{
if(used[findd(i)]==0)dfs(findd(i));
}
for(ll i=1;i<=m;i++)dp[i]=1;
for(auto i:tops)
{
for(auto j:adj2[i])
{
dp[j]=max(dp[j],dp[i]+1);
}
}
memset(used,0,sizeof(used));
for(ll i=1;i<=m;i++)
{
if(used[findd(i)]==0 && (ll)adj1[findd(i)].size()!=0 && deg[findd(i)]==0)
{
if(dp[findd(i)]==n)dfs1(findd(i));
}
}
for(ll i=1;i<=m;i++)
{
if(color[findd(i)]==0)cout<<"?"<<endl;
else cout<<"K"<<color[findd(i)]<<endl;
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
21 ms |
24064 KB |
Output is correct |
2 |
Correct |
22 ms |
23936 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
129 ms |
37224 KB |
Output is correct |
2 |
Correct |
139 ms |
37480 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
33 ms |
27500 KB |
Output is correct |
2 |
Correct |
35 ms |
27636 KB |
Output is correct |
3 |
Correct |
35 ms |
27636 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
291 ms |
51908 KB |
Output is correct |
2 |
Correct |
296 ms |
55520 KB |
Output is correct |
3 |
Correct |
270 ms |
55264 KB |
Output is correct |
4 |
Correct |
372 ms |
63316 KB |
Output is correct |
5 |
Correct |
369 ms |
66900 KB |
Output is correct |