oj.uz

Submission #241116

# Submission time Handle Problem Language Result Execution time Memory
241116 2020-06-22T20:20:41 Z computerbox KOVANICE (COI15_kovanice) C++14
60 / 100
 485 ms 57052 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 24064 KB Output is correct
2 Correct 21 ms 24064 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 40168 KB Output is correct
2 Correct 162 ms 40164 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 27128 KB Output is correct
2 Correct 35 ms 27256 KB Output is correct
3 Correct 39 ms 27128 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 485 ms 57052 KB Output isn't correct
2 Halted 0 ms 0 KB -