oj.uz

답안 #1078423

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1078423 2024-08-27T17:06:02 Z Trumling 기지국 (IOI20_stations) C++14
21 / 100
 624 ms 1016 KB 
#include "stations.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std; 

typedef long long ll;
#define pb push_back
#define F first
#define S second
#define enter cout<<'\n';
#define INF 99999999999999999
#define MOD 1000000007
#define all(x) x.begin(),x.end()

#include "stations.h"
    #include <vector>
    #include<bits/stdc++.h>
    using namespace std;
     
    #define F first
    #define S second
    #define all(x) x.begin(),x.end()
    typedef long long ll;
    #define pb push_back
    #define INF 99999999999
 
	ll nn;
    vector<vector<int>>g;
    ll here=0;
	vector<int>labels;
 
	void dfs(int i,int id,int start,int pre)
	{
		
		labels[start]=i*1000 + id;
		//cout<<labels[start]<<' ';
 
		for(auto x:g[start])
			if(pre!=x)
				dfs(i,id+1,x,start);
 
		return ;
	}
 
    vector<int> label(int n, int k, vector<int> u, vector<int> v) {
    nn=n;
 
 
    	g.assign(n,vector<int>());
    	labels.assign(n,0);
		vector<bool>cnt(n,0);
		here=0;
    	for (int i = 0; i < n-1; i++) {
    		g[u[i]].pb(v[i]);
    		g[v[i]].pb(u[i]);
 
    		if(g[u[i]].size()>2)
    		here=u[i];
    		if(g[v[i]].size()>2)
    		here=v[i];
 
			if(g[u[i]].size()==2)
			cnt[u[i]]=1;
 
			if(g[v[i]].size()==2)
			cnt[v[i]]=1;
 
		}
		if(g[here].size()<=2)
		for(int i=0;i<n;i++)
		if(!cnt[i])
		{
			here=i;
			break;
		}
 
		//cout<<here<<'\n';
 
		for(int i=0;i<g[here].size();i++)
			dfs(i,1,g[here][i],here);
		//for(int i=0;i<n;i++)
		//cout<<labels[i]<<' ';
 
    	return labels;
    }
     
    int find_next_station(int s, int t, vector<int> c) 
    {
 
    	if(c.size()>2)
		{
			ll ans;
			for(int l:c)
			if(t>=l && (t-l)<1000)
			{
				ans=l;
				break;
			}
			return ans;
			
			//assert(0);
 
		}
			
		
 
		int mini=INF;
		for(auto x:c)
		mini=min(x,mini);
 
		if(t<s)
		return mini;
 
		if(s/1000==t/1000)
		return s+1;
		else
		return mini;
 
 
    }

Compilation message

stations.cpp:25: warning: "INF" redefined
   25 |     #define INF 99999999999
      | 
stations.cpp:11: note: this is the location of the previous definition
   11 | #define INF 99999999999999999
      | 
stations.cpp: In function 'std::vector<int> label(int, int, std::vector<int>, std::vector<int>)':
stations.cpp:79:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |   for(int i=0;i<g[here].size();i++)
      |               ~^~~~~~~~~~~~~~~
stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:25:17: warning: overflow in conversion from 'long int' to 'int' changes value from '99999999999' to '1215752191' [-Woverflow]
   25 |     #define INF 99999999999
      |                 ^~~~~~~~~~~
stations.cpp:107:12: note: in expansion of macro 'INF'
  107 |   int mini=INF;
      |            ^~~
stations.cpp:99:11: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   99 |    return ans;
      |           ^~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 362 ms 684 KB Output is correct
2 Correct 319 ms 684 KB Output is correct
3 Correct 593 ms 684 KB Output is correct
4 Correct 442 ms 684 KB Output is correct
5 Correct 420 ms 688 KB Output is correct
6 Correct 324 ms 684 KB Output is correct
7 Correct 299 ms 684 KB Output is correct
8 Correct 1 ms 776 KB Output is correct
9 Correct 2 ms 776 KB Output is correct
10 Correct 1 ms 1016 KB Output is correct

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 344 KB Invalid labels (duplicates values). scenario=0, label=10
2 Halted 0 ms 0 KB -

Subtask #3
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 388 ms 940 KB Output is correct
2 Correct 291 ms 684 KB Output is correct
3 Correct 591 ms 684 KB Output is correct
4 Correct 445 ms 684 KB Output is correct
5 Correct 399 ms 684 KB Output is correct
6 Correct 322 ms 684 KB Output is correct
7 Correct 284 ms 688 KB Output is correct
8 Correct 2 ms 776 KB Output is correct
9 Correct 2 ms 768 KB Output is correct
10 Correct 0 ms 776 KB Output is correct
11 Correct 410 ms 684 KB Output is correct
12 Correct 343 ms 768 KB Output is correct
13 Correct 328 ms 932 KB Output is correct
14 Correct 339 ms 684 KB Output is correct
15 Correct 26 ms 776 KB Output is correct
16 Correct 36 ms 768 KB Output is correct
17 Correct 73 ms 716 KB Output is correct

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 586 ms 684 KB Output is correct
2 Correct 445 ms 684 KB Output is correct
3 Correct 410 ms 684 KB Output is correct
4 Correct 2 ms 768 KB Output is correct
5 Correct 3 ms 768 KB Output is correct
6 Correct 0 ms 760 KB Output is correct
7 Correct 449 ms 684 KB Output is correct
8 Correct 624 ms 684 KB Output is correct
9 Correct 459 ms 684 KB Output is correct
10 Correct 431 ms 940 KB Output is correct
11 Incorrect 0 ms 344 KB Invalid labels (duplicates values). scenario=5, label=2
12 Halted 0 ms 0 KB -

Subtask #5
0 / 61.0

# 결과 실행 시간 메모리 Grader output
1 Correct 392 ms 940 KB Output is correct
2 Correct 297 ms 940 KB Output is correct
3 Correct 607 ms 684 KB Output is correct
4 Correct 475 ms 684 KB Output is correct
5 Correct 410 ms 684 KB Output is correct
6 Correct 351 ms 684 KB Output is correct
7 Correct 304 ms 684 KB Output is correct
8 Correct 1 ms 776 KB Output is correct
9 Correct 1 ms 768 KB Output is correct
10 Correct 1 ms 768 KB Output is correct
11 Incorrect 2 ms 344 KB Invalid labels (duplicates values). scenario=0, label=10
12 Halted 0 ms 0 KB -