Submission #241116

#	Time	Username	Problem	Language	Result	Execution time	Memory
241116		computerbox	KOVANICE (COI15_kovanice)	C++14	60 / 100	485 ms	57052 KiB

kovanice

#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];

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,ll sig)
{
  used[v]=1;
  sig1[v]=max(sig1[v],sig);
  
  for(auto to:adj1[v])
  {
	if(used[to]==0)
	{
	  dfs1(to,sig);	
    }  
    else
    {
	  push[to]=max(push[to],sig);	
    }
  }	
}

void dfs2(ll v)
{
  used[v]=1;
  sig1[v]=max(sig1[v],push[v]);
  
  for(auto to:adj1[v])
  {
	if(used[to]==0)
	{
	  push[to]=push[v];
	  dfs2(to);	
    }  
  }	
}

ll mx=0;
vector<ll>el;

void dfs3(ll v)
{
  used[v]=1;
  mx=max(mx,color[v]);
  el.pb(v);
  for(auto to:adj[v])
  {
	if(used[to]==0)dfs3(to);  
  }	
}


int main(){
FLASH;
cin>>n>>m>>k;
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=='=')adj[cis1].pb(cis2),adj[cis2].pb(cis1);
  else adj1[cis1].pb(cis2),deg[cis2]++,adj2[cis2].pb(cis1);
  
}

for(ll i=1;i<=m;i++)
{
  if(used[i]==0)dfs(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[i]==0 && (ll)adj1[i].size()!=0 && deg[i]==0)
  {
	if(dp[i]==n)dfs1(i,1);
	else dfs1(i,0);  
  }
}

memset(used,0,sizeof(used));

for(ll i=1;i<=m;i++)
{
  if(used[i]==0 && (ll)adj1[i].size()!=0 && deg[i]==0)
  {
	dfs2(i);
  }
}

memset(used,0,sizeof(used));

for(ll i=1;i<=m;i++)
{
  if(sig1[i]==1 || push[i]==1)
  {
	color[i]=n-dp[i]+1;  
  }	
  else color[i]=0;
}

for(ll i=1;i<=m;i++)
{
  if(used[i]==0)
  {
   el.clear();
   mx=0;
   dfs3(i);
   for(auto j:el)color[j]=mx; 	
  }
}

for(ll i=1;i<=m;i++)
{
 if(color[i]==0)cout<<"?"<<endl;
 else cout<<"K"<<color[i]<<endl;	
}





return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 40 / 40
• Subtask 3: 10 / 10
• Subtask 4: 0 / 40